I saw a fairly cheap HP printer today (model 2050 I think). It was branded "ePrint" and I think that, at one point, Apple said that any HP ePrint printer would be AirPrint compatible.
One of the lists showed the D110 as compatible. I bought one for my SIL from Amazon at $60, and Best Buy has them for $70. I think we will see more compatibility with other models soon. iOS 4.3 might add a bunch.