Well, I haven't actually tried this yet but it shouldn't be very difficult. Mind that I don't have a copy of the final game yet, just a pre-release version, so if things have slightly different names or anything, that could be an explanation for it.
1) Copy one of the existing entries of default\gamedata\govern.txt (e.g. Communism, as long as it isn't Anarchy, that's a slightly non-standard government) and paste it at the end of the that file. Now change all the stats you want to change.
2) If you have a picture (if you don't, skip this step) to accompany your government (for the Great Library), make sure it's an 16-bit tga file. Save it in default\graphics\pictures.
3) Open uniticon.txt and copy one of the government entries of that file and past in anywhere else in that same file. Now rename all entries. FE if you copied the Communism entry and are adding Aristocracy, replace all instances of COMMUNISM with ARISTOCRACY, presuming that's the name you used in the govern.txt file and the name you'll use in the Great Library section. If you have a picture rename the FirstFrame and Icon sections to the name you gave your picture, if you don't have one, rename them NULL.
4) Now open english\gamedata\Great_Library.txt to add your government to the Great Library. Again, copy one of the existing entries and add it anywhere in the file. Rename the 'titles' of the GL sections (GOVERNMENT_ARISTOCRACY_PREREQ, GOVERNMENT_ARISTOCRACY_STATISTICS) and change the gameplay/historical sections. Look at the existing GL entries to see how you can make links to other sections of the GL if necessary. Don't forget to update the entry on the advance that enables your new government as well (the [ADVANCE_name_STATISTICS] section should say "Gives <link>Aristocracy</link>").
5) Open english\gamedata\gl_str.txt and add the line GOVERNMENT_ARISTOCRACY "Aristocracy" (and for other governments as well of course).
6) Well, basicly your government should work now, so start up your game and try it out. The only problem now is that the AI doesn't know how to handle your new government and will ignore it. So once you've tested it and you know it works for you (and you're happy with all the settings), there's one more step:
7) To make the AI use your government as well, open default\aidata\strategies.txt and search for Government. There should be 8 or so sets of government settings, one for each personality in the game. Add your new governments to those personalities you think should use your settings (scroll up one or two screens to find what personality you're dealing with) and place it where you want it to be used (I think the AI will always choose the highest government in the list). The lines with // in front of it are comments and ignored by the program, so you can ignore those too. Here the example for Economist personality:
Government GOVERNMENT_VIRTUAL_DEMOCRACY
Government GOVERNMENT_CORPORATE_REPUBLIC
Government GOVERNMENT_DEMOCRACY
Government GOVERNMENT_THEOCRACY
Government GOVERNMENT_TYRANNY
Say you want to replace Theocracy with Aristocracy for this government, this should be what it should look like:
Government GOVERNMENT_VIRTUAL_DEMOCRACY
Government GOVERNMENT_CORPORATE_REPUBLIC
Government GOVERNMENT_DEMOCRACY
Government GOVERNMENT_ARISTOCRACY
Government GOVERNMENT_TYRANNY
Well, that should be all. It's not impossible a minor mistake here or there, so if this doesn't work right away, don't give up yet
