I am working on it at the mo... nearly there,
www.sub-laser.co.uk/shop
I'm using WCM's ezrecommends with a couple of mods.
When the cart is empty, several products are shown at the bottom of the cart page. On step 1 of the checkout, recommended products are also shown, based on the cart contents' linked products.
I think that ezrecommends is the best way ahead to achieve this.