We report on a search with the IceCube detector for high-energy muon neutrinos from GRB 080319B, one of the brightest gamma-ray bursts (GRBs) ever observed. The fireball model predicts that a mean of 0.1 events should be detected by IceCube for a bulk Lorentz boost of the jet of 300. In both the direct on-time window of 66 s and an extended window of about 300 s around the GRB, no excess was found above background. The 90% CL upper limit on the number of track-like events from the GRB is 2.7, corresponding to a muon neutrino fluence limit of 9.5x10^-3 erg cm^-2 in the energy range between 120 TeV and 2.2 PeV, which contains 90% of the expected events.