Have them list references of other ponds they have built. Talk to as many owners as you can - see if the ponds leak, if they got the design they wanted, how costs compared to estimates, how long did he take to complete and were there any unreasonable delays (weather you can't help) - are they happy? Inspect the ponds if possible.
Pond experience may not be necessary - my guy did his first pond for us, learned with us from the local Gov't pond expert, and the dam is perfect - but significant excavating experience is, IMO.
Ask how they are going to core the dam and compact the clay there in. If they don't seem to understand the concept, be ware.
Have them dig test holes first to insure you have proper soils - enough clay, nothing but (hopefully) small amounts of gravel or sand. Understand that test holes are money you spend up front to make sure you don't waste much bigger sums later on trying to build a pond that won't hold water.
Will they build the pond you want or just a smooth hole in the ground? (Or is that actually what you want?) To a good dozer operator without bottom structure experience, putting ridges and holes and structure in the bottom is almost blasphemy.
Utilize as many other sources of info as possible on your own - NRCS office (if amenable), topo maps, the experts here - to know things like what your watershed acreage is and should be to fill and maintain your pond. Buy Lusk's "Basic Pond Management" book and as many PB back issues with Mike Otto articles as possible.
Realize that an estimate is just that. The best way to do your pond right at the lowest possible cost is to do it right from the start. Changes you realize you want, odd pockets of bad soil, bedrock where you don't expect it, and other unforeseen problems are best fixed while building, even if the initial cost goes up. An excavator who finishes on a fixed budget despite encountering problems like these is apt to "finish" with the pond unfinished, the problems unfixed. Straightening them out later will probably cost more, possibly much, much more, than fixing them at the beginning.