Delete the "C:\Program Files\Firaxis Games" folder (assuming that where you installed it), delete the "C:\Documents and Settings\<your username>\My Documents\My Games\Sid Meier's Civilization 4" folder if it is still there.
Go into the registry (Start->Run->regedit) and navigate to HKEY_LOCAL_MACHINE\Software. If this is the only game you have from Firaxis delete the key called "Firaxis Games" otherwise delete any sub keys of Firaxis Games" starting with "Sid Meier's Civilization 4". Navigate to HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Uninstall and delete the following keys {4377F918-E6C9-4ECA-A7F5-754B310B7ED8}, {CFBCE791-2D53-4FCE-B3FB-D6E01F4112E8}, {3E4B349F-10B5-4586-9D99-489A90A8B228} and {32E4F0D2-C135-475E-A841-1D59A0D22989}. Not all of them may exist.
Also delete the following folder if it exists:
"C:\Program Files\InstallShield Installation Information\{CFBCE791-2D53-4FCE-B3FB-D6E01F4112E8}"
NB. The InstallShield folder is hidden by default. You will need to configure Windows Explorer to show hidden files and folders.