The Laser Interferometer Space Antenna (LISA) will be able to detect massive black hole mergers throughout the visible Universe. These observations will provide unique information about black hole formation and growth, and the role black holes play in galaxy evolution. Here we develop several key building blocks for detecting and characterizing black hole binary mergers with LISA, including fast heterodyned likelihood evaluations, and efficient stochastic search techniques.