Tu problema se googlea con el nombre de "sticky footer".
Complementando la sugerencia de Ag666 (que funciona perfecto):
A este lo probé y doy fe que funciona:
http://ryanfait.com/sticky-footer/
A este también y es excelente porque deja libre de trucos y limpito al html al basarse en jquery (necesita js activado para caminar):
http://jsfiddle.net/cristian_cena/4awwx/
Saludos.