I purchased a Newertech replacement battery from the web site mentioned above for my 3G 40Gb iPod. The battery was delivered to my home within two days.
The video on the company's web site really clarifies the procedure. It's a good thing too, because the printed instructions packed with the battery are microscopic. I literally could not read them -- even with a magnifying glass.
The replacement was completed from beginning to end in less than five minutes. The entire process was much simpler than anticipated and I am very pleased with the results.