I never did this before, so the most difficult part of getting a VPN connection working was about finding the right solution.
The source of my inspiration being apt-cache search, I first tried the Gnome Network Manager but the version in Efty Edge is so buggy that it was barely usable.
Then, I tried kvpnc. I could not get through all the menus it presented and make it work.
At that point, I gave up on graphical tools and went back to basics by googling for a HOWTO on linux+vpn+windows. My today's luck drove me to an openswan-based tutorial. After meditating for around an hour on IPSec configuration, I desperately returned to Google in a quest for a simpler solution and, within 15 minutes, I stumbled upon the pptp-client which had a ... surprise-surprise! Debian HOWTO. After that, it was just a matter of 5 minutes to set up and test the first configuration.