"Losslessly" and "not losing any quality" are two very different things, H.
AVCHD is a highly compressed format. And, because of the way virtually every video program works, the file is converted and recompressed when you output it -- even if you choose an output format that's identical to the AVCHD you put it. It's just not possible to edit and process AVCHD natively.And in any re-compression of a video, there is loss.
However, this loss doesn't not necessarily mean loss of quality. You can, for instance, output a BluRay disc of an AVCHD video and the quality of both videos will be virtually indistinguishable.
Does that help?
As for the upgrade question -- that's more a question for Adobe. Since technically every "upgrade" is actually an entirely new program, you can certainly do it technically. However, I'm not sure you can get version 9 for a discounted price, based on your purchase of version 3. But maybe. Adobe is often very accommodating with this kind of thing if you contact them directly.
I came across 'provides native support for avchd'; what does it mean?
This means that PrE can input and edit the AVCHD files, without the need to work with intermediate CODEC's. Many NLE (Non Linear Editor) programs first will convert the AVCHD files to something else, that it can edit. PrE does not need to do this in more recent versions. It just Imports the AVCHD material, and edits it.
Steve has given you about all considerations on the Output end of things, and as usual, has done an excellent job of it.
The one consideration would be "how do you need to deliver the output files?" He cites BD, which is a common and good example. If, however, you have other needs, please list those, as there might be some considerations, or workflows that would benefit those. So, and to a degree, the answer is "it depends."
PS - As an aside, the GUI (Graphical User Interface) underwent a major change from PrE 3 to PrE 4, and some additional changes with PrE 7, 8 and 9. Since you would be coming from PrE 3, I strongly recommend Steve's excellent books on PrE 9. They will get you up to speed on the changes. Some things have been moved about, and a few names have been changed. PrE 3 was closer in visual design, to PrPro. When I came from PrPro to PrE 4.0, I have to admit that I was a bit lost at first. Steve, and some others, helped me adapt to the new GUI. The mechanics were very similar, but I had to learn to look in a few different places. As I still work extensively in PrPro, when I open up PrE, I need to sit quietly and "get my mind focused." Steve's books will help with the transition, and are highly recommended.
For your several questions...
One... download and try the 30-day free trials
Two... read in the user guides
CS5 User Guides - online and PDF (see link in upper right corner at individual pages)
P-Elements 9 http://help.adobe.com/en_US/premiereelements/using/index.html