I'm currently building minimal debian system for my backup & samba server. I just happen to have 512MB brand new CF card and CF-to-IDE reduction. This is my story of how to get (fully) working debian system on it.

• Install without any choices. This will install approximately 300MB system. Yey! (Also, you need to do the usual, ext2, noatime and this kind of stuff – you can probably save some space by using smaller inodes/blocks)
• Add internet mirrors.
• Install stuff you really need: vim, less
• Purge locales: apt-get install localepurge (this frees approximately 44MB, so its worth it!)
• Remove some docs you don't use and don't install them anymore. You can do this by adding those lines to /etc/dpkg/dpkg.cfg.d/01-nodoc and removing them:

path-exclude /usr/share/doc/*
path-exclude /usr/share/info/*
path-exclude /usr/share/man/??/*

• Remove locale sources from /usr/share/i18n. You will end up by having only those (yeah, and you can blacklist the rest as above):

./
./SUPPORTED
./charmaps
./charmaps/UTF-8.gz
./locales
./locales/en_US
./locales/en_GB
./locales/iso14651_t1
./locales/iso14651_t1_common
./locales/iso14651_t1_pinyin
./locales/i18n
./locales/translit_combining
./locales/translit_neutral
./locales/translit_circle
./locales/translit_cjk_compat
./locales/translit_cjk_variants
./locales/translit_compat
./locales/translit_font
./locales/translit_fraction
./locales/translit_hangul
./locales/translit_narrow
./locales/translit_small
./locales/translit_wide

Alternatively, you can just comment every line in /etc/locale.gen and hope it won't break anything, or tell the system to use C locale.. Haven't tried that.

• Now you should have place for anything else… apt-get install samba (and the space is gone like that.. puff!)
• To get ro root, you need to mount these things as tmpfs (or use some overlay or what you like), so put this in /etc/fstab:

tmpfs /tmp tmpfs rw,nosuid,noexec,relatime 0 0
tmpfs /var/log tmpfs rw,nosuid,noexec,relatime 0 0
tmpfs /var/run tmpfs rw,nosuid,noexec,relatime 0 0
tmpfs /var/lib/dhcp tmpfs rw,nosuid,noexec,relatime 0 0

You will need to remount root after boot and before samba (TODO: Simple init script)