Many phenomena, ranging from biology to electronics, involve flow over rough or irregular surfaces. We treat such surfaces as random fields and use an immersed boundary method (IBM) with discrete (random) forcing to solve resulting stochastic flow problems. Our approach relies on the Uhlmann formulation of the fluid-solid interaction force; computational savings stem from the modification of the time advancement scheme that obviates the need to solve the Poisson equation for pressure at each sub-step. We start by testing the proposed algorithm on two classical benchmark problems. The first deals with the Wannier problem of Stokesian flow around a cylinder in the vicinity of a moving plate. The second problem considers steady-state and transient flows over a stationary circular cylinder. Our simulation results show that our algorithm achieves second-order temporal accuracy. It is faster than the original IBM, while yielding consistent estimates of such quantities of interest as the drag and lift coefficients, the length of a recirculation zone in a cylinder's wake, and the Strouhal number. Then we use the proposed IBM algorithm to model flow over cylinders whose surface is either (deterministically) corrugated or (randomly) rough.