Why is ice made from boiled water clear? A common trick to make clear water ice is to boil pure water prior to freezing it. Why does that work and what are the white inclusions in ice that was made from unboiled tap water?

 A: I'm really winging this one because the last time I did an equilibrium calculation was 35 years ago! But I'm fairly sure of a partial answer (see discussion at end).
A gas's solubility in water (or liquid generally) almost always decreases with increasing temperature. This phenomenon is explained in a way very like the explanation of the increase in evaporation rate of a liquid with temperature.  Gases dissolve in liquids because the gas molecules find a lower energy state bound to the liquid. The higher the temperature, the greater the proportion of the gas molecules with thermal energy greater than the binding energy for the dissolution process. So a greater proportion of the gas molecules can escape from liquid: the chemical equilibrium for the dissolution reaction shifts to favor free molecules more than bound ones with increasing temperature.
The boiling of a liquid lowers the concentration of dissolved gases through the above effect. Normally the shift of equilibrium back to favor dissolved gases with decreasing temperature would mean that, on cooling, the liquid would take up as much gas as is driven off in the boiling process. The trick with clear ice is that the liquid is frozen too quickly for the gas dissolution process to complete - it is frozen irreversibly so that it is a long way from equilibrium as it cools - with the result that there is a nett expulsion of gas from the liquid by the boiling before freezing process. Once the liquid is frozen, the gas can no longer dissolve in it, so you have clear ice.
Note that this answer is incomplete: it does not answer why the gas dissolved in the liquid forms the bubbles it does when the liquid freezes, as in the right hand image of your question. This answer only explains the absence of the gas needed for the clouding process, so a full answer needs to explain why the dissolved gas comes out of solution to form bubbles as the ice freezes.
A: The short answer: Cloudy ice is caused by gases (mainly nitrogen and oxygen) dissolved in the water that come out of solution when the water freezes. The small bubbles trapped in the ice cause the white appearance. Boiling the water removes the air dissolved in it, producing clear ice as a result. Assuming that other impurities don't produce the same cloudy effect.
The long answer: 
Impurities present in water:


*

*Gases: Water at 20°C normally contains about 15 ppm dissolved gases, which is the equivalent of 1 volume of air per 50 volumes of water. These are the same gases present in air, but not in the same proportions since some are more soluble than others: it's about 63% nitrogen, 34% oxygen, 1.5% argon and 1.5% carbon dioxide.

*minerals: Tap water contains dissolved minerals, mainly Ca and Mg. They can be present in the form of bicarbonates: $Ca^{2+}({HCO_3}^-)_2$ and $Mg^{2+}({HCO_3}^-)_2$ (these only exist in solution, not as solid substances), and as calcium and magnesium sulphate. If the water passed through a water softener, the Ca and Mg ions may have been replaced by (twice as many) sodium or potassium ions.
The effects of heating the water:


*

*removing dissolved gases: higher temperature favors endothermic reactions (Le Chatelier's principle). For the gases present in water, dissolution (at room temperature) is an exothermic process, so their solubility decreases when the water is heated. The solubility of gases doesn't reach zero at boiling point, nor does it necessarily decrease over the whole temperature range. For nitrogen in water, the enthalpy of dissolution becomes positive around 75°, and its solubility increases above that temperature. 
At 100°C, solubility of air as a whole is $0.93 * 10^{-5}$, about half the solubility at 10°C, $1.82 * 10^{-5}$. 

*removing dissolved minerals: Heating the water promotes the conversion of soluble Ca and Mg bicarbonates to insoluble carbonates ($2 {HCO_3}^-$ → $CO_3^{2-} + H_2O + CO_2$) which will come out of solution (as limescale). The sulphates (sometimes referred to as "permanent hardness"), and the sodium or potassium (bi)carbonates stay in solution. 
The effect of boiling:


*

*Solubility of gas in liquid not only depends on temperature, it is directly proportional to the partial pressure of the gas. When boiling, the gas phase in contact with the water is no longer the air, but the water vapor (in the bubbles and close to the surface). In those bubbles the partial pressure of the gases will be close to zero, so gas molecules will still leave the liquid phase (and the increased surface area and the movement of the water speeds up the process), but hardly any will return. Given sufficient time, the water vapor will remove most of the gas. Boiling is basically the equivalent of degassing by purging: removing a gas (oxygen usually) from a solvent by bubbling an inert gas through it. 


How do gases make ice "milky/cloudy"?


*

*During freezing, the ice layer starts at all sides of the cube and grows inward. Water molecules fit the crystal lattice and will adhere to it, other molecules won't (but if the ice grows faster than the gas molecules can diffuse away, they will get trapped). The concentration of gases (and other impurities) in the remaining liquid rises, the solution becomes supersaturated, microbubbles start forming. All these get trapped in the ice, giving it a milky appearance. 

A: This answer was meant as a comment to @WetSavannahanimal aka Rad Vance but it is rather long and I hit the character limit.
The reason for the opaque center should be due to the manner in which the water volume is freezing. Presumably the solution is not mixed and the outside freezes first forming a crystalline (ice) wall through which the gas cannot escape. As the wall thickens gas is released from the water that solidifies into the central solution that remains. This concentrates the gas in the remaining liquid in the centre. When the gas concentration in this solution hits the saturation value for the liquid at it's current state some of it exits the solution forming the cavities, simultaneously some ice should form, returning the solution to the saturation concentration. This is repeated until all the water is frozen. 
The observation that clear ice is made buy bubbling gas through it as it freezes, indicates that mixing of the solution allows the saturated gasses to escape from the surface of the total water volume as the solid forms rather then forming in the center.
Now one might ask the question why is it that there isn't just a single bubble. The first reason, from a bulk solution point of view, is that the water is freezing incrementally forming bubbles as it goes. It is really oscillating about the equilibrium state of the solution, that is the gas saturation point of the freezing solution. The exact conditions of this point will vary slightly as the liquid freezes. The pressure that the ice in the center froze at is likely larger then the pressure at which the surface ice froze at for instance, similarly there is a the temperature at which it froze might also vary. There is probably also a concentration effect, that is as this equilibrium point shifts about the gas saturation point will shift about, this change in concentration also affects the freezing point a little. There are about four effects (Temperature, Pressure, Volume and Gas Concentration) at play during the freezing. The second effect, from a finite volume point of view, is that locally about the cavity the water might experience a "rush of gas" which could locally freeze a film of water encapsulating the bubble hence the final complex arrangement of cavities and not the formation of a single bubble.
Now it might just be possible to see these freezing point differences using the polarizer trick. I've only seen this with clear plastics till now but it should work here aswell. Next time you go to a movie get a pair of 3d goggles. take out the two polarizing lenses and hold them on either side of the ice cube by rotating them a little you should see the internal crystalline structure of the ice as a mess of swirly lines. You should probably see more of a swirl or a scattering in the center near the bubbles indicating the localized changes in crystal structure. You should compare this to the transparent cube.
There is a further trick you can try. If you controlled the freezing of the ice by some degree you could control the formation of the bubbles. For instance our ice trays are plastic and we tend to have a clear upper layer with bubbles forming in the lower part of the cube. I suspect the plastic is retaining it's heat and delays the freezing of the bottom and the side of the cube. I suspect if one warmed or even cooled the ice tray before forming the ice one might see a different formation of cavities (As shown in the second image here for example). If you used a metal ice tray you should see the effect you have observed. If you combined a metal and a plastic ice tray together you might get more bubbles closer to the plastic side. You might even be able to get a polka dot/explosion/blobbing effect by dotting glue inside a metal tray, or holding a metal rod within the volume as you froze it. Although you could just be adding points for the gas to form and escape resulting in clear cubes. Alternatively you might just get a carrat (hat). This Fellow seems to have done a lot of the leg work for you. Beneficially he seems to enjoy drinking his experiments afterwards (YMMV).
If you are really interested you should see if NASA did any freezing experiments in space it might show other methods by which one could control bubble formation. Similarly you might find high speed camera footage of freezing during which you should see some interesting effects as the bubbles form (Though it's a bit of a contradictory use of these cameras and I doubt the people who own them have thought to use them for this purpose). 
