Removing the ads from the new Kindle Fire HD is a fairly simple process.

First make sure to root your device, the method here should be quick and painless: http://forum.xda-developers.com/showthread.php?t=1893838

Now just open up a terminal and do the following:

adb shell su cd /data/data/com.amazon.kindle.kso/
rm -r ./adunits touch adunits

Now the lockscreen should just show the stock photos.