I have done some testing on an old computer with 256 MB.
It can, barely, boot the live CD all the way with Bianca Gnome. Install not tested but should be possible.
With Cassandra BETA012 it won't go past an empty desktop.
Conclusion: You should (preferably) have more than 256 MB
Edit by Husse February 2009
This is now specified in the release notes and at least the Fluxbox edition will have an explicit helper for your memory needs