See this document for ReducingDiskFootprint.
It includes instructions about how to disable apt caches, have any package installations skip installing the documentation or locales that don't apply to your system. It suggests how you can modify log rotation setups to minimize log storage.
My dpkg config file for small storage system looks like this.
# block documentation
# keep copyright files for legal reasons
# lintian stuff is small, but really unnecessary
# block non-us locales
Obviously you need to be very careful about the package you select. Avoid those huge meta-packages that include tons of crap. You may need to consider using equivs to make empty packages in some cases where a dependency is set, but you don't need the functionality the dependency makes possible.