How to organize iPhone contacts into groups directly on the iPhone?

Can't do on the phone itself, must do in a supported contact application on your computer, then sync the groups to your phone. Either that, or you look for a third-party contact application in the app store that provides this functionality, or use iCloud:

http://support.apple.com/kb/PH2667?viewlocale=en_US

Use something like copytrans contacts - run the app on your computer and connect your iPhone.

When the "From PC" group appears in the program window, right-click and choose delete:

This will delete only the group not the contacts themselves.

To add new groups to your iPhone Contacts select on "New group" instead and type in the name of the new group you want created:

<Link Edited By Host>

there are some apps, where you can add/delete groups directly on iPhone and easily assign contacts to groups.

For example "Contacts In : Import CSV & Manage Groups". See here: http://csvcontacts.wordpress.com/iphone-groups-broadcast/. As bonus you get all contact management things (deletion, creation) and ability to send broadcast SMS and e-mails and quickly clean up your contacts.

Swipe group to delete - only group itselt will be deleted, not the contacts! Then you can create new groups, assign contacts to group directly on iPhone, no need for PC connection. The groups which are created are "native" iPhone groups and you will see them in any other applications (e.g. in native iPhone address book).