Proxy servers do a good job of hiding your real IP address. But it depends on the program you use and how you use it. If you want to hide your IP from a Web host, any simple proxy will work. Most will send your data through a proxy server, and will use a different server with each session. That alone is enough to hide your IP address. But it's not enough to truly keep you private, since repeated hits during the same session through the same proxy server can be easily traced by anyone with the tools to do it. Using a simple Web proxy can burn you if you use the same proxy to check e-mail and for other Internet activities (background checks for things like Windows Update, syncing, and those daily checks for updates from installed software), as over time (usually about 3 sessions, sometimes less) these tracing tools will nail your real IP address and location. But for most people who don't do anything illegal on the Internet, for general Internet activity and Web surfing, a simple Web proxy is fine. However, as Greg noted, even through a proxy application, the browser will still identify your real IP (and MAC address) to the host. It just won't be displayed, and it takes a little digging to find it inside the raw data packets.
The next level up from standard proxy servers are the applications which do automatic proxy switching, where a different proxy server is used for each and every URL request. Meaning, every page you view on a Web site will look like the request is coming from a different IP address. IP and MAC addresses are hidden with most of these proxy applications, as both the IP and the MAC are virtual.
Beyond that, if you want truly anonymous surfing and other things, you need to be using an encrypted cypherpunk remailers and something like the I2P anonymous network layer, which uses a variety of VPN I2P packeting tunnels and PGP to encrypt all end-to-end communications thereby completely hiding the IP addresses of the sender and the receiver from each other and any third party observers. I have an e-mail server in Norway, for example, where all my e-mails in and out are automatically encrypted through a series of proxies and remailers, which adds an additional layer of security. Regardless of where I post, all my Usenet postings can be traced back only as far as a non-existent Usenet server in Ciudad Juarez. An I2P layer can be set up to encrypt and proxy HTTP, HTTPS, Usenet, Telnet, TCP/IP, IMAP and POP3, file sharing, i.e., all Internet activities. You don't see much written about it in the mainstream (or even the alternative) press, but Wikileaks owes its very existence to the fact that Julian Assange was an early adopter and participant within the Cypherpunk Movement. There's a reason why PGP is classified as a restricted export munition by the US government, and why it is illegal in many countries. It's because PGP and layering networks like I2P provide absolute privacy and anonymity.
If you have a business, using a VPN and a proxy server together isn't overkill, it's actually less secure, as the VPN would have to, by necessity, have holes for the proxy server. VPN allows you through the firewall, but a proxy server would
