I plan on assembling the following FM transmitter to be used as a
listening device in a legal manner:

http://www.broadcastwarehouse.com/p/BW/FM-Transmitters/LCD-PLL-1-W-Exciter?pid=12

I plan on simply hooking it up directly to a microphone and antenna. 
Unfortunately, I need the device to run on battery power.  The power
requirements listed in the specs indicate that the device needs
12-15Vdc 300mA max.  Please recommened a good configuration of
batteries (wired in parallel/series, whatever) that can be used with
this device.  Cost is not an issue, but longevity of operation is. 
Small size would be nice as well.  Thanks.

although someone might cringe at the following, you have a couple of options.
Two of these in series...
http://www.radioshack.com/product.asp?catalog%5Fname=CTLG&category%5Fname=CTLG%5F011%5F002%5F001%5F000&product%5Fid=270%2D391

or stack 4 or 5 tall of these ...
http://www.radioshack.com/product.asp?catalog%5Fname=CTLG&category%5Fname=CTLG%5F009%5F015%5F001%5F000&product%5Fid=23%2D189

600mAh (milliAmp Hours) means it'll run 600 milliamps for an hour (at
least, this is how I read it. I could probably be wrong).
Your project pulls 12-15Vdc 300mA max so you could get about 2 hours
out of it, but probably more if you use 5 of them because you have a
3V range.

http://www.radioshack.com/product.asp?catalog%5Fname=CTLG&category%5Fname=CTLG%5F009%5F014%5F006%5F000&product%5Fid=23%2D144
12v remote control battery...

If length of time is more critical than size ... :)
http://www.radioshack.com/category.asp?catalog%5Fname=CTLG&category%5Fname=CTLG%5F009%5F014%5F008%5F000&Page=1

I am not a Google Answers Researcher.

two words: motorcycle battery.

It'll last you days and days.  Also, it's pretty small.  You can limit
current by adjusting your wire diameter.  It's not that small, but it
lasts for freakin' ever!