After reviewing a bunch of "NoSQL" style document-based / key-value storage systems, I decided to move forward with four of them and install them on production and demonstration machines.
On the production machines, I stuck with Debian's "testing" repository, currently dubbed "Squeeze". As such, I installed MemcacheDB and Redis.
On a demonstration machine, I temporarily added the unstable repository, "Sid", as well as the MongoDB repository for the stable Debian distribution, "Lenny" (which required I add the official Lenny repository as well). With these extra repositories, I was able to install tokyotyrant and mongodb. :-)