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.