Ground states and domain walls are investigated with exact combinatorial optimization in two-dimensional random field Ising magnets. The ground states break into domains above a length scale that depends exponentially on the random field strength squared. For weak disorder, this paramagnetic structure has remnant long-range order of the percolation type. The domain walls are super-rough in ordered systems with a roughness exponent ζ close to 6/5. The interfaces exhibit rare fluctuations and multiscaling reminiscent of some models of kinetic roughening and hydrodynamic turbulence.