For logic gates, should I just get a bunch of NAND and NOR gates? I understand that any of the other logic gates can be made of combinations of these.
Most simple projects seem to use NAND gates. And while you can make any gate out of the NOR or NAND, it doesn't hurt to have a few of each type of gate in your junk box if you intend to build things with discreet logic chips.
Maybe a good project would be to try to make all the other gates from these two.
That would be a good learning experience. Your breadboard will come in handy; avoid soldering a bunch of experimental circuits together because you'll be tearing them apart just as quick as you build them.
I'll look into op-amps, they seem to be really important.
Yes they are. The LM358 and LM324 are legacy chips that good for getting your feet wet but have been superseded by better chips such as the MC34074, etc. The LM741 is ancient.
I have experience with programming languages, and I've read a couple introductory books on electronics
You'll probably want to eventually get into micro controllers. PICs and AVRs are pretty popular. So don't buy TOO many discreet logic chips.
And what about transistors? The variety available is frightening, I don't know where to start.
Some popular numbers for small signal transistors in North America are 2n3904, 2n3906 & 2n2222. And then there are MOSFETs....
What should I do about a power supply? Build one? A good first project?
It is a good project as long as you are confident with working on AC powered mains. I don't know your level of expertise, but I wouldn't recommend it for a beginner from a safety point of view. I have a proper power supply in my closet, but actually use a 12V wallwart feeding a 7805 mounted on the backside of my breadboard for 5V projects. Keeps my limited workspace clear.
As far as just going out and randomly buying parts, I wouldn't recommend it. A better approach would be to find a project you want to build and order a few extra parts for it. ie: most suppliers have a price break at 10, 25, and 100 lot quantities and you'll find it won't cost you much more to order 10 transistors vs 5. Then if you blow a part up you'll have a spare on hand and if not, something for the junkbox.