Whilst browsing this question, some of the answers mentioned that certain registrars will replace your whois information with their own. Can anybody provide details on which registrars offer this service?
The many and varied companies offering this service appear to be well summarised by this Google search.
Generally, anyone who offers Private Registration will 'hide' your information. That is still really just a thin veil of security, for US based registrars at least, as a subpoena will make them open up fairly quickly.