We design an efficient algorithm for studying problems in fluid-structure interaction on distributed-memory computer clusters using the standard and generalized immersed boundary (IB) equations. The algorithm utilizes a pseudo-compressibility method recently proposed by Guermond and Minev that uses a directional splitting strategy to discretize the incompressible Navier-Stokes equations, thereby reducing the linear systems to a series of one-dimensional tridiagonal systems. This endows our algorithm with the computational complexity of a completely explicit method and excellent parallel scaling properties. We demonstrate the effectiveness of our IB algorithm through detailed numerical and performance studies. For several model problems, we report the accuracy and convergence rates of our algorithm in two and three dimensions. These results are then compared with alternate projection-based IB algorithms. The execution time and scaling properties of our algorithm are then investigated and we discuss the performance benefits over alternative approaches. We conclude with an investigation of the dynamics of flexible fibers in a shear flow using the generalized IB method. In our simulations, we reproduce the orbit classes observed experimentally by S. G. Mason and co-workers. Lastly, using parallel tiling techniques, we simulate dilute suspensions that contain as many as 256 fibers.