First eBay example:
http://www.ebay.ca/itm/Panasonic-NCR-18650-PF-2900-mAh-3-6V-Li-Ion-Battery-with-TABS-/262076648181
And a page where someone takes apart a laptop battery pack
http://www.candlepowerforums.com/vb/showthread.php?246699-Tutorial-Laptop-Battery-Pack-18650-Extraction"
As I said, you need the ones with the tabs. You can't solder wires directly to the battery. The standard ones like the following
can't be used because they don't have tabs[/U][/U].
http://www.ebay.ca/itm/18650-GTL-Li-...-/161845188714
Some eBay sellers offer a service to weld tabs to the batteries when you buy them. Just look around for the best deal.
After you build a new battery pack and install it, you can use the device as before and charge it using the original charger.