What is the significance of _domainkey.foo.com prefixes? (pic, mailo, k1, etc)

Here are short sweet answers that you requested:

How does that querying server know which to query?

That prefix is called selector. The receiving server know which DNS record to query by looking into the DomainKey-Signature header containing the cryptographic signature. Among many useful information, there are the selector and domain values. For example:

DomainKey-Signature: a=rsa-sha1; s=smtp; d=example.com; c=simple; q=dns; b=JOc8ZszniSbVoGVyOfAKCdLXyuU4zGffruD4doXSlEG2q8Ldyd00laHRNiYzRv+Z;

selector + "_domainkey" + domain = smtp._domainkey.example.com

Why isn't there just one standard prefix?

There isn't one standard prefix, because in some scenarios you want to have the option to configure multiple different DomainKeys records (e.g. you have two SMTP servers and you want each one to use it's own DomainKeys policy).

Isn't _ an illegal character?

As you can see, it's not :-)

And here are some reading materials ;-)