I take 20 minutes from my time to respond to this question ...

This is the setup for console connection.

For a graphical setup just use Kppp
1. First of all what modem do you have ? Internal or External ? 1.1 For internal modems you need to know what driver fit for your modem. Is possible to don't be supported by linux (or in this way was 2 years ago

). Anyway you can use a utility to discover your modem:
For Redhat distros you have kudzu.
For Mandriva you have harddrake.
For Debian you have discover.
I'm not very sure about Redhat / Mandriva because I didn't use this distros for ages, but in this way it was when I used them last time.
1.2 For External modems is all much simple. You only thing what you need to do is to set the speed of the port or stuff like this ( man setserial

).
2. Check if your modem is working !Attention for windows users. Under linux you don't have com1 com2 com3 com4 ... you have /dev/ttyS0 (com1) /dev/ttyS1 (com2) etc
Use
minicom for this mission. Is the bigbrother of the Windows Hyperterminal
Set your speed of your serial connections (115200 etc) of your terminal and type ati/atz/etc in minicom console. If you get an OK or some info's about modem then is all ok.
3. Setting up the connectionFirst you need to have a username and a password from your ISP.

Check if you have ppp software installed
under Redhat or derived distros :
rpm -aq | grep 'ppp'
under Debian or derived distros :
dpkg -l | grep ppp
If you will see something like:
ii ppp 2.4.3-20050321 Point-to-Point Protocol (PPP) daemon
ii pppconfig 2.3.11 A text menu based utility for configuring pp
If not you will need to install them.
Under debian with a simple command you can install all what you need:
apt-get install ppp
Under Redhat you need to use urpmi or other utilities to do that.
Now set your username and password in /etc/ppp/pap-secrets
<username> * <password> *
Now configure your modem/ppp parameters in /etc/ppp/peers/YOURISPNAME
ttyS0 115200
lock
crtscts
auth
modem
user <username>
defaultroute
connect '/usr/sbin/chat -v -f /etc/ppp/dial.script'
And now configure your script for dial-out(/etc/ppp/dial.script):
ABORT "BUSY"
ABORT "NO CARRIER"
ABORT "NO DIALTONE"
ABORT "ERROR"
ABORT "NO ANSWER"
"" ATZ
OK ATDT YOURISPPHONENUMBER
CONNECT ""
Now simple launch from you console:
pppd call YOURISPNAME
4. Debugging Just look in /var/log/syslog.
For a more verbose output just add in your /etc/ppp/peers/YOURISPNAME on a new line: debug.
For more parameters of pppd just look in: man pppd
I hope this is useful for you.
Regards