Should I choose 32 or 64 bit for Linux?

You should install 64-bit linux. Even though there are ways for the 32-bit kernel to address more than 4 GB the applications will still have a 3 GB limit.

You can run a 64-bit kernel and a 32-bit distribution which will give you full access to 4 GB or more of RAM, without the performance penalty of PAE. This is what I do on my machine. Debian has linux-image-amd64 available for i386. Unfortunately Ubuntu doesn't, you'd have to compile your own kernel there, and I don't know if other distributions have packages.

Having said that, for new installations I'd recommend 64-bit as performance is better, so long as you can live with hacks for 32-bit-only binaries like Skype and some browser plugins. RPM distributions have OK support for this at the moment, while Debian and Ubuntu don't, but are working on multi-arch support now, with a first release expected for Ubuntu 9.10 this year.

Here is one overview from LinuxForums.

I would hesitate if you do a lot of work with niche or developing tools written in entirely compiled languages. Many of the projects I'm interested in, like LDC, are only beginning to support 64 bit. Personally I'm holding off, but I'm holding off on more RAM too, so that's not an issue for me.

32-Bit can only use less than 4 GB for a single process, but it can use more for the whole system. There are not many non-server applications on Linux that will want that much RAM that I can think of.

You will just need to install the PAE (Physical Address Extension) kernel:

sudo sudo apt-get install linux-headers-server linux-image-server 

and then reboot. Run top or free and you should more ram. I recommend 32-Bit for desktop users.

I'd install a 64-bit version and potentially something like VirtualBox so I can run a 32-bit version in parallel in case I'd need some software that is only available in 32-bit.

You won't be able to make use of more than 4 GB of memory using a 32-bit kernel without jumping through some hoops like PAE which is IMHO better avoided.