VoIP - also called Internet telephony or IP telephony - is the popular term for a number of technologies that enable voice to be carred via the Internet's IP-based data network instead of networks dedicated to voice. This doesn't necessarily mean that a VoIP call is the only time that your voice is carried in digital form from your mouth to the listener's ear. Both local and long-distance "traditional" phone companies have used combinations of analog and digital networks to carry calls over the PSTN (Public Switched Telephone Network) for a number of years without making a big deal of it.
The move to digital by the telephone companies (telcos) was primarily cost driven for purposes of "pair gain" - the ability to squeeze more subscribers onto a single circuit. (Your telephone uses only two wires - a "pair" in telephone terms - that enable your phone to do its job.) These digitized voices were carried over telephone service providers' private networks, however, never touching what we know as the public Internet.
The key differences with VoIP are that the digital conversion takes place before your voice leaves wherever you're making the VoIP call from, and your phone lines (and local telephone company) aren't involved - unless you're using them for a DSL-based broadband connection. With VoIP, your digitzed voice usually travels over the public Internet, although this isn't a VoIP requirement. Many companies still make significant revenue selling VoIP services that travel over private networks owned by them or their customers.
It's interesting to note that the recent frenzy is actually VoIP's second attempt at mass-market acceptance. The first consumer VoIP wave actually took place in early 2001 with Net2Phone and Linksys partnering on the BEFN2PS4. This was the first product from a major consumer networking product company to enable consumers to use a regular analog phone to make digital calls over the Internet.
Unfortunately, for a number of reasons, VoIP didn't hit critical mass and the hype died down. Net2Phone is still in the VoIP business, but is definitely taking a lower-key approach this time, leaving the hype generation (and big advertising budgets required) to Vonage and others.
NOTE: As this article was written, the BEFN2PS4 was still up on Linksys' website. But the company told me it has been discontinued, replaced by the RT31P2.