A giant ablative shield, combined with EM-based deflection.
Current thinking for theoretical starships has been quite partial to using huge chunks of ice for debris protection, because it is already available outside our gravity well (just go snag a comet!), potentially re-shapeable (just melt it!), and it's a valuable source of hydrogen (for fuel) and oxygen (for breathing). Neal Stephenson's recent hard sci-fi novel Seveneves explores this concept, albeit at planetary-orbit, sub-light speeds.
Impact at relativistic velocities, on the other hand:
For a starship moving at 0.3 c, a typical grain of carbonaceous dust
about a tenth of a micron in diameter should have a relative kinetic
energy of 37,500,000 GeV. [Our ship] will run into about thirteen of
these dust particles every second over every square meter of frontal
area. Travel fast enough and even small grains of dust behave like energetic cosmic rays. (source)
For passive shields, several possibilities have been examined -- aluminum, titanium, graphite, graphene, even beryllium. This might be placed many kilometers ahead of the spacecraft. Any mass that makes it through the "bumper" would end up being high-energy spray of charged particles that could be deflected by some sort of EM beam or large magnetic field. One novel concept for an additional layer of defense was deploying a dust cloud in advance of your ship, which would theoretically vaporize larger particles and render them susceptible to the active (EM) shield, before they could damage the ship.
An equal or bigger concern than physical debris is the variety of radiation you'll encounter while moving at relativistic velocities. Metal hull shielding is workable up to a third the speed of light, but much faster and it has to be tens of meters thick. The old trick of encasing yourself in a water tank shell would also provide shielding.
The blog Centauri Dreams -- which I've linked to throughout this answer -- has at least three posts examining this exact problem and referencing whitepapers on the subject; I highly recommend checking them out for more details.