Put a bevel modifier on it. Leave the inputs, just click "apply".
step 3 of 9
Add an Subdivision surface 4 times
step 4 of 9
Switch to "Sculpt Mode" and select the "Clay" brush
step 5 of 9
Now, go a little wild, and add/subtract some matter on the edges of the cube, 'til you get something that looks like an ice-cube.
step 6 of 9
Add a few spheres which will act as air-bubbles. This just gives a better look
step 7 of 9
For me, the main point in this contest is the material who's gonna be used. So I tried around, and this is what I think is the closest to reality. I noticed, that the light-refraction-index (IOR) is near to glass (I took 1.450). A list can be found here(see below):