You can use the same techniques as above-water landscape generation - but simply apply different principles. Here are some examples:
Basic Landscape
Underwater landscapes have much more pronounced features than above-water. This is likely because (as far as I know) the ocean beds are more tectonically active. None-the-less you will need to tweak the generator/perlin so that you get immensely deep ravines and so forth.
Erosion/Weathering
Typical above-water landscape generation relies on the fact that there is infrequent rainfall that runs downhill: contrast this with underwater where you have permanent erosion (so exaggerate the erosion effect) and where it also/partially runs in the direction of the local currents (so don't only send it downhill: create some currents before eroding). However keep in mind (depending on the depth of the area you are eroding) that the amount of deposits (sand) might be relatively small so you would reduce the weathering effect.
This type of erosion could likely get very expensive to the degree where I would consider skipping it and just use classical erosion.
Features
Due to the depth variance (shallow to extremely deep) the features on the seabed vary widely. At relatively low depths you get coral reefs and so forth, at the other end of the spectrum (trenches) you get volcanic vents and so forth.
Summary
Read up on weathering and tectonics under water and try and simulate that. Remember you don't need to perfect it and create the perfect seabed - just something convincing so that the player doesn't think to question it. On my first attempt I would concentrate on:
- Ravines and other unique tectonic features.
- Classical erosion instead of underwater erosion (only add underwater erosion if it isn't convincing enough).
- Features like vents or coral would likely be the most convincing aspect.