In My Documents \ My Games \ (whatever you called the Civ IV directory) there should be a set of user-specific info for Civ IV. There's a CivilizationIV.ini or something like that. FullScreen is 0, 1, or ask - ask means you'll get a dialog every time you start the game asking which you want.
There's a bunch of other funky stuff in there, but not sure what exactly they all are.
Edit: That's specifically under the My Documents, to prevent confusion - in addition to the main install. So I have it installed in D:\Games\CivIV, and the ini for me is under C:\Documents and Settings\celeval\My Documents\My Games\CivIV