That depends on your current skills (programming, art etc.)
It seems to be a consensus that
this tutorial is a good place to start.
Basically there are 4 main components which you can mod in Civ4:
Art (which I know hardly nothing about) - everything from textures (images) to 3D meshes to animations (e.g. for units and leader heads). This is less of a gameplay modding component, I guess.
XML which is the file format in which most the data the game uses is held. This is a text format and you can easily edit it in any text editor (I recommend notepad++). By modifying these files you can change basically everything which is not behavioral in the game - which units are there, what their properties are (strength, cost etc.), which buildings are there, which civilizations/resources/terrain/improvements/ game speeds etc. etc.
The XML and art should be enough to make any mod which doesn't change the behavior and interface of the game.
In addition, you have two components which require some programming knowledge, but this can be learned:
Python is a scripting language, which means it is parsed at runtime - while the game is running. These scripts control many things - starting with the way the game looks (screens, interfaces) up until actually coding some of the logic of the game (e.g. Random events and their effects). See
this tutorial for starting Python modding.
The DLL is the core of the game's logic, and Firaxis was kind enough to release its source code (you might sometimes see people refer to it as SDK). DLL stands for Dynamically Loaded Library, and is a file which is created by taking a lot of C++ source code files, and compiling them to machine language. If you want to change the basic way the game behaves, or add new features to the core logic of the game (e.g. how combat is done, victory conditions etc.) - this is the place.
If you don't already know C++ this can be a little more complicated than the previous components, but you can definitely learn this. You can check out
my tutorial on compiling the DLL, and it has some links inside for actual C++ programming and Civ4 programming specifically.
A beginner's project?
Some people say you should start small - tweak a unit here, add a building there and see how it goes.
I say - if you want to start modding you probably already have ideas of your own, and you're not in it to "become a modder". Start with them, even if they are a bit complicated, and work your way through them using the help of other modders. You'll enjoy more and have higher motivation to continue. Ask questions, get stuck, read useful tutorials, read tutorials which have nothing to do with your problems (but you'll only find out after you've read them), experiment, and most importantly - have fun.
EDIT: Wow, I wrote a manifest...