Why does gold react with cyanide and sodium hydroxide
Flotation and treatment of gold with $\ce{NaCN}$ in the presence of air are two distictive steps!

Flotation yields fine particles of gold (and pyrite) at the surface of a flotation tank, attached to foamy bubbles while the rest of the minerals sink to the bottom of the tank.

Flotation does not rely on differences in specific density, but on hydrophobicity!

In the cyanide treatment, the following process - similar to what Uncle Al described for the seawater case in his answer - occurs:

Solid gold is oxidized, the cations are bound by cyanide anions and form a water-soluble complex:

$$\ce{4Au + 8NaCN + O2 + H2O -&gt; 4Na[Au(CN)2] + 4NaOH}$$

In order to reobtain solid gold, the $\ce{Au(I)}$ in the cyano complex $\ce{[Au(CN)2]^-}$ has to be reduced to $\ce{Au(0)}$ again. This can be done either by adding zinc dust, according to  

$$\ce{2Na[Au(CN)2] + Zn -&gt; Na2[Zn(CN)4] + 2Au}$$

or electrochemically.