There are a few separate pieces to this question: how to tell the compiler/linker to generate and preserve "debug information" (mapping between source code and object code), how to tell the compiler to compile the code differently to make debugging easier (think of assert() and #ifdef _DEBUG), and whether the precompiled libraries you link into your project include debugging information.
-Zi (flag to the CL compiler to tell it to generate debug information) is the equivalent of gcc's -g flag.
(There are other forms of the -Z option: -ZI if you want the "edit and continue" support in the Visual Studio IDE, but if you're using the IDE you're probably using its interface to the compiler settings instead of manipulating them directly, and -Z7 if you want the old CodeView-format debug information; whenever I've invoked CL directly it's always been -Zi that I wanted.)
Note that using the -Zi (or -ZI) option will generate a .pdb file per directory, usually, but when you link code together, it may have come from .obj files represented in different .pdb files, and you also want to combine those separate .pdb files into a master one representing the code you linked together -- this is what the -debug switch for the linker is for.
Also note: this may sound counterintuitive, but always use -Zi (for CL) and -debug (for link.exe). Even for code you're going to release. It doesn't increase the size of your executable, or give away secrets to your customers, since the debug information goes in a separate .pdb file (which you won't ship to customers). If there's any chance you're ever going to have to debug it, you're going to want the .pdb. (-Zi isn't even incompatible with optimizations, though -ZI is. So you might want to compile your "debug" builds with -ZI, and your "release" builds with "-Zi -O2".)
As for the libraries: you don't strictly need to match the debug/release property of the C runtime library with whether your code includes debugging information, but it's usually a good idea -- if you're going to debug the project you want to be able to debug all of it, and if you're not going to debug it you don't need the extra weight. Using debug/release versions of a given library won't affect whether it has debug symbols available (hopefully, if whoever compiled the library understood the point I made in the previous paragraph), but it will affect things like assert and extra #ifdef _DEBUG code in that library.
This goes for all libraries you link with, but especially for the C runtime library -- Microsoft added extra error-detection code to malloc() and free(). So if anything in your project is using the debug flavor of the CRT library, all of it should be.
The /M options (/MTd and /MDd) are weird and magic, in my opinion -- they're just aliases for a complicated set of other stuff going on behind the scenes. Take /MDd for example, documented to "Defines _DEBUG, _MT, and _DLL and causes your application to use the debug multithread- and DLL-specific version of the run-time library. It also causes the compiler to place the library name MSVCRTD.lib into the .obj file." Here, it's affecting both the preprocessor (defining _DEBUG and some other preprocessor symbols) and the linker (it actually puts a #pragma comment(linker) in your source code). If you care about what's going on and don't understand it, this can cause real problems -- I've seen a lot of projects that don't use the IDE get bogged down in warnings about both msvcrt.lib and msvcrtd.lib being linked in, etc. By the time you understand how to use these (/M options) safely, you don't really need them any more! I prefer to make things explicit: specify "-D _DEBUG" directly where I need it, specify which libraries to link with explicitly (and use -nodefaultlib), and then the /M options aren't needed.
