How does landing performance differ on water vs. ice vs. paved/grass runways?
The takeoff and landing performance on different surfaces varies with condition - for example, a wet or snowy paved runway will have different braking and rolling acceleration performance than a dry paved runway. We can make some general/broad statements, but it's important to note that the specific conditions on any given day will play a large part in aircraft performance.

That said, here are some general/broad statements:



Water (and snow on skis)

Water is the odd surface in the group: It is not a runway in the traditional sense. If you "land" an aircraft with traditional hard-surface landing gear (tires) on water it is not a landing, but rather a ditching and is covered under emergency procedures.  

Landing a seaplane (either a "flying boat" hull or something with floats) on water is a different beast from a landing on land, and indeed an entire different rating on your pilot certificate. Everything you ever wanted to know about seaplanes can be found in the FAA Seaplane handbook (FAA-H-8083-23), which also covers aircraft equipped with skis for landing on snow (which is in many ways similar to landing a float-equipped airplane on water).



Pavement (Asphalt, Concrete, etc.)

Paved surfaces are the baseline standard by which "land" landings are judged.  The performance charts and tables in your POH are generally given with the assumption of a dry, paved, level runway that is free of contaminants.

Wet or Contaminated Pavement

Wet, snowy, or icy pavement primarily affects braking performance: An aircraft will not be able to stop as quickly on wet pavement as the tires may hydroplane/skid with aggressive braking. This video gives a good overview of the effects of wet pavement, and while it's primarily aimed at Part 25 Transport-category aircraft/operators the same basic considerations apply for light General Aviation aircraft.
Your aircraft performance charts may discuss operations from contaminated runways, but if they do not cover this situation some rules of thumb for landing performance on wet or contaminated pavement are:


Wet Pavement (no puddles): Multiply landing distance by 1.4
Wet Pavement (w/ puddles): Multiply landing distance by 2.3
Snow on Pavement: Multiply landing distance by 1.6
Icy Pavement: Multiply by 4.5 (expecting braking to be largely ineffective)


Similarly allowances must be made for takeoff performance (additional resistance on the tires from contamination on the runway) - The usual takeoff rules of thumb work here ("Have 70% of your takeoff speed by the time you've used 50% of the runway."), with the caveat that you need to consider braking distances in the event of an abort: Aborting halfway down a 3000 foot runway when you expect to need 1800 feet to brake to a stop would be a Bad Thing.



Grass

Grass is the traditional "soft field" surface, though well-maintained grass with good drainage on a dry day may not be all that "soft" when you land on it.
As with a contaminated runway the major difference is rolling resistance: You will stop a little faster on dry, level grass than you would on an equivalent paved field because the grass offers more resistance to the tires, and you will take longer to accelerate to takeoff speed for the same reason.

Again, your aircraft performance charts may include figures for soft field / grass field takeoffs/landings (this is often given as a percentage of the paved surface figures). If your performance charts don't include soft field / grass field data there are again some rules of thumb you can use:


Short grass: Add 10% to the takeoff roll
Long grass: Add 25% to the takeoff roll
Wet grass (Soft Field): Add 35% to the takeoff roll
Muddy field: Add 50% (or more) to the takeoff roll


Paved surface landing distances work well for grass fields, with the exception of wet grass (which can be treated as a soft-field landing on wet pavement to account for your tires skidding on the wet grass).

Gravel

Though not strictly a subset of grass, considerations for gravel runways are similar: Increased rolling resistance during takeoff (as your tires push the gravel around), and diminished braking effectiveness on landing (in particular extreme braking on gravel can lock a wheel and leave a rut, as it would on a soft grass field).
Soft field takeoff and landing distances would be appropriate to use for gravel runways.



Ice

Ice is an interesting surface: It's hard, but it has a very low coefficient of friction. On clean ice your takeoff distance will be similar to pavement, but your landing distance will be significantly increased since your wheel brakes will be largely ineffective.
As for icy pavement you can plan on a landing distance of 4.5 times your paved runway landing distance (or more), and you will likely be nosewheel steering or differential braking will have reduced effectiveness for directional control (tailwheel pilots will be at a distinct advantage here, as the rudder work they do in a normal takeoff or landing is very similar to what's required to keep the aircraft going straight on ice).

Contaminated ice (standing water, snow, etc.) impose penalties similar to contaminated pavement, with the added caveat that water on ice is an incredibly low-friction surface (to illustrate this drag your finger across an ice cube dry, then do the same with a little bit of water on the surface of the ice cube) -- the increase in landing distance required would be substantial if landing on a wet ice runway.



Unique surfaces

While the list above covers the vast majority of runways you're likely to encounter there are some "unique" surfaces out there (for example perforated steel planking which is sometimes used to construct temporary runways can become a special challenge when it rains as friction on the metal is reduced by water and mud squirting up through the perforations with certain types of underlying soil).
If operating from a "unique" surface the best resource you have is other pilots who routinely operate from that surface, or at least have some experience with it -- they can tell you what to expect under different conditions, and you can plan accordingly.