When I bought my Macbook Pro I was told that when Lion came out I could get the upgrade for free. How do I go about doing this? I've searched the Apple.com website extensively and can't find information on this.
The Lion up to date program is public. It currently says the deadline to ask for a free copy is August 19, 2011 and macs purchased on or after June 6, 2011 are eligible.
Otherwise, Mac OS X 10.7 Lion will cost you $29.99, and is available on the Mac App Store (link). You can also go to an Apple store to download it (if you have a slow connection), and Apple will be making a version on a USB thumb drive available for $70. (More info here.)
To answer the more general question as to what Apples policy is for software updates for Macs purchased in the run up to a major release: Historically, Apples 'Up-to-Date' programs for free or heavily discounted upgrades have been offered to those who have purchased a new Mac within 2 weeks (i.e. the duration of the standard return policy) of a major OS update. This is primarily done to prevent those users from simply returning and rebuying the machine on launch day. Additionally, at times, Apple has announced up to date availiability for everyone who has purchased a machine between the announcement of a specific release date and that release date. This is fairly uncommon however, and if they do so for Lion, you'll hear about it.
The program initially allowed for people that bought macs on or after June 6, 2011 had a filing deadline of August 19, 2011. A follow-on program for macs purchased after July 21, 2011 has a 30 day after purchase claim window.
Both programs were documented at http://www.apple.com/macosx/uptodate/ . It looks like there was an August 2011 deadline to ask for a refund / free copy of Lion.
Historically, Apple honors upgrade / price matching requests for the time of the new purchase return period (2 weeks in the US) and has occasionally offered fulfillment plans to lengthen that window to encourage sales once a firm release date is announced. If you buy a new mac the day of a new software release (and until the new software gets included in the build at the factory) the box has a "drop in kit" installed with the new software free of charge.
Of course you could always ask for a free upgrade, but since the window is 2 weeks, you might not convince someone to give you a free upgrade if the purchase was several months before the eventual release. If you have a good relationship with your seller - shoot them a mail or stop by the store to let them know to contact you if they can help with pricing when it releases.
Also, the price for 10.6 was $29 for 10.5 owners so depending on the release price details, that may affect how far back Apple chooses to offer gratis copies of the new Lion software.
Yes. See this for more information.