When you go and find a cheap low end Linux virtual server, the criteria usually involve price (very important!), location (for low latency SSH access), virtualization (Xen vs. OpenVZ?), etc. However the “bit-ness” is rarely looked at. Most current Intel and AMD processors can run 64bit instruction sets, and many virtual server vendors are also offering VPSs in either 32bit or 64bit.
However, contrary to conventional wisdom, bigger is not necessarily better. Do you really have a need for 64 bit on your 64MB VPS? Maybe (but not likely), and it will actually be more prudent to stick with the good ol’ 32 bit, because for exactly the same application, it actually uses less memory on 32bit than 64bit!
Currently I’ve got two 64MB Xen VPS — one running 32bit Debian Etch at Datarealm, and the other running 64bit Ubuntu Hardy at RapidXen. Two have very similar stack — syslogh-ng, xinetd with dropbear, Vixie Cron, Postfix, Lighttpd and PHP. The 32bit Debian actually runs a few more — gld for greylisting and 2x PHP/FastCGI processes (which are at 6MB each). Guess what, I actually have more memory left with my 32bit Debian VPS than my 64bit Ubuntu VPS!
It makes sense that 64bit programs use more memory. Integers and pointers are now double the size. So you are not only allocating more, you also need a bigger stack for bigger pointers. Result? Less free memory for other applications or cache.
You can still make a 64bit 64MB VPS do a lot of tricks, but if the only reason to get 64bit is huge address space + ability to do massive matrix manipulation, then you are going to need a lot more memory anyway.
Meanwhile, for a small web head or a redundant MX, 32 bit ought to be enough