Here's how I would do it...and I grant that this may be overcomplicated.
1) Set up a script that spools all existing customers into Post Affiliate Pro (PAP) and gives each of them a unique ID
2) Set a similar script to run when a new customer places an order (enter new customer into PAP database and generate referral ID)
3) Set up a page on my customer portal that allows each customer to see his/her referral ID and gives a bunch of choices to refer friends (email with a plugin that finds all friends in address book for services like Gmail/Yahoo; banner ads; text link). Pull the link by sending an auth token with the customer ID to the PAP API.
^ In #3 above I'd do this instead of referring them to the PAP customer portal, which seems overkill for this scenario, and would set up a multiple login nightmare.
4) Integrate PAP and my shopping cart/customer database so when a customer refers another customer and that referral is approved, it shows up as a credit in their account.
Of the above, #4 is the tricky part, and depends on their shopping cart/billing software. It may be easier to hire a VA to manage this, at least at the beginning, esp. if the customer database is homegrown.
Disclaimer: PAP or iDev may have easier ways to do this; this is based on my own experience with PAP, which was admittedly a different integration. But as a programmer, this is the working thesis I'd start from.