The instructions Flash posted work, I just did this to two new key FOB's I bought off eBay and it worked like a champ!
But as noted, you must have two working keys to program new keys.
In my case, the buttons on one of my FOB's quit and a new battery did not fix it, so I ordered two new key/FOBs off eBay.
I cut them and used the two old keys that still worked OK in the ignition switch to program the new ones per the instructions.
If you do not have two keys that still function OK in the ignition switch (buttons do not have to work), then a locksmith or a dealer with an ODBIII is your other choices....

_________________
Supporting Vendor and Moderator of LOST05 Jeep Liberty CRD Limited 
Ironman Springs/Bilstein/Shocks
Yeti StgIV Hot Tune
Week's BatteryTray
No FCV/EGR
Samcos/ProVent
SunCoast/Transgo
Carter Intank-pmp
2mic.Sec.Fuel Filter
Flowmaster/NO CAT
V6Airbox/noVH
GM11 Bld.fan/HDClutch
IronrockArms/wwdieselMount98 Dodge Cummins 24 Valve