I suppose as a Community extension for Magento Connect:
I also suggest posting it and all the juicy details in a Wiki Post (if you want to make it freely available)
You can upload a community / commercial extension in your My Account area (top right near your shopping cart icon on the Magento page - mouse over username)
As for actually “physically” packaging your extension, I would just zip up all relevant files(keep file structure!!!) to a .zip file.