I seem to remember something a Puppeteer (Nessus?) said about paying them with "Stars".
I couldn't find any mention of this in Wikipedia, so maybe I'm not remembering correctly.
I've found two answers:
There are "crowns" that are used as currency, teleporting from one place on Earth to another is 1/10 of a crown (very little money). http://www.docstoc.com/docs/6475419/Fictional_currency
The one you're likely interested in: "star" is a currency that replaced the previous UN "mark". 1/2 star can buy a book tape, and 1/10 of a star can mail a wallet. http://www.freewebs.com/knownspace/s.htm/
The testimony of the many stories that involve Outsiders and the logical structure of their existence suggests what kinds of payment they would be interested in.
If you read enough of the many Known Space stories you'll find that the Outsiders do quite a lot of business with warm species for as little contact as they have with them, so we have several chances to see how that work.
They seem to accept payment in
Information (as suggested by zephyr) or technology (though in the Fleet|Juggler|Destroyer|Betrayer of Worlds books it is made clear that the races of Known Space have little to offer in this respect with an exception related to reason (3)). Because those are things that they can take with them, and re-sell again and again.
Credit expressed in a local currency that they can expect to use (as geoffc notes), which means offered by races that are politically stable and sufficiently well established to have a expectation of lasting a long time.
That said, their willingness to sell the hyperdrive to We Made It suggests that they are willing to take a chance on up-and-coming races. After all their marginal costs are low, and the potential for profit is fairly high.
Spoiler reason (read the Fleet of Worlds series first)
Protection of their juvenile stage: the star seeds.