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. :-)