Adding a Webpart gallery grouping using WSP package is easy. Switch to WSP view in Visual Studio 2008 and modify the "your webpart.xml" file.
WSP view is new feature in VseWSS 1.3 (VseWSS - Visual Studio Extensions for Windows SharePoint Services).
Example Xml file: