Building a gift recommendation engine

This is just a thought, but you could set up a hot-or-not type of system for products: place two products side-by-side, and ask a user which they'd prefer to have. You could even offer a coupon or other discount to the extent that the user will accumulate more discounts as they offer more information. There's no good way to ensure honesty when providing these ratings, so features generated from it should only be used as secondary or tertiary evidence. The primary evidence, as you correctly noted, are the site's purchase history and the user's purchase history.

You could probably extrapolate additional proclivities and predilections based on the user's demographic information, as well. For example, someone in Nebraska probably wouldn't have as much of an interest in ocean kayaks as someone in Florida.

This sounds like a simple classification problem. Without access to any personal purchase history you should be aiming to build up a training set. This may entail having to sit and decide which gifts are appropriate for a few thousand users.

After that you can start using more collaborative filtering approaches as you can track when the users agree to purchase the gifts. You will be able to do much better if you can infer purchase histories per user even if you are recommending gifts to new users. That information will give insight into what items are bought together.

There is several sites that already tackle this problem. One of the best new ones is giftivo.com (plug). Go read some machine learning programming books and you can get yourself started.