Update Ubuntu BEFORE trying to install Steam!
I see a lot of people who have just installed Ubuntu and are having problems getting Steam installed. If you have just done a fresh install of Ubuntu, it is VERY IMPORTANT that you apply all the Ubuntu updates before installing Steam. This is doubly important on a 64-bit system.
To install the updates, click on the little gear in the upper-right hand corner, select "Software Up to Date"->Check->Install Updates. If you have a freshly installed system, there should be LOT of updates (hundreds) and you'll need to reboot.
I really think this will solve most of the fresh install problems on this forum. Please try this and then post if it is still not working.
I am glad to see so many people trying to install Linux. We will try to make this fresh install a little more bullet-proof in the future, but there is critical functionality in those updates that Steam needs.
Update: This should all be resolved with the new packages propped this weekend (Feb 24th)