The (almost definite) reason that people are having problems is that they're saving their contacts as Google ones, rather than phone ones. Not their fault, there's a default setting that's likely to be doing it for them.
If your contacts are Google ones then, as said above, you can add them to Google groups through your Gmail account on the PC. But you can't add them to the phone's preset groups. The only way that you'll manage that is to change every contact to be a phone one (easiest way that I've found is to export them all to SD card, delete all from the phone, then import from SD card, choosing to save them as phone contacts when asked).
Obviously, to prevent future problems, if you're going to do this you also need to change the default setting to Phone. This can be found in Contacts, More, Settings, "Save new contacts to".
Having said that, my personal preference is to keep them as Google contacts & use Google's grouping, so that they sync with my Outlook contacts.