Puddle holes are a form of wind holes. They are common during windy thaws on ice that is less than a roughly 6" thick. The mechanism is a warm wind blows and warms the surface water to the downwind end of the puddle. This The return flow along the bottom melts ice off the bottom of the puddle. There is usually a connection between the puddle on the surface and the water underneath the ice that replaces surface water that gets blown out of the downwind end of the puddle. Shallow puddles with no connection to the water under the ice are likely to get blown down in high winds rather than staying in the same place so they can erode a hole. The erosion mechanism appears to work best once the puddle gets to be a couple inches deep, allowing significant ripples to form on the surface and a strong return flow at the bottom of the puddle. Johan Porsbey pointed out that solar heating can be a significant part of heating the puddle, particularly later in the season. Water absorbs or transmits sunlight almost completely while an ice surface is more reflective (particularly when the sun is at a low angle).
The puddles holes form a number of ways. The following are a couple of common examples.
When the ice sheet warms it expands putting compression stress in the sheet. This results in local shallow buckling of the sheet, often with a mostly tight crack acting as the hinge point. Puddles form where the sheet has buckled down, creating a puddle that is resistant to being blown down wind. In a thawed state the ice sheet usually has pores through the sheet at grain boundaries. Wind gusts tend to pull water up through the ice sheet and lulls let it go back down. This enlarges the pores over time. A warm wind on a few inches of ice can turn the puddle into a hole in as little as a day.
Puddle holes can be hard to see on thawed state with lots of other shallow puddles on the surface of the ice. Once it gets colder they often develop rims of white splash out ice and/or catch blowing snow around their edges. Both of these features make them easier to spot (see the picture above). It is common for there to be a long line of holes scattered along the one particular crack while many other visible cracks do not have holes associated with them.
A thick, water saturated, snow drift is heavy enough to depress the ice enough to let water seep to the surface at each side. These puddles often form in pairs with one hole on each side of the drift ('saddlebag holes') .