How to recenter an object's origin?
Press Shift + Ctrl + Alt + C (perhaps the longest shortcut in Blender) and select Origin to Geometry. Or, instead, open the Toolshelf by pressing T and press the Set Origin button in the Tools tab, subsection Edit.

Depending on how you imagine the 'Center' of your object, you might instead want to choose Origin to Center of Mass. The difference is that it calculates the center point based on the volume of the mesh, rather than the average location of vertices as Origin to Geometry does.

Visually, the difference is this (blue dot is the new origin point):



UPDATE for Blender 2.8

Press the Object button at the bottom of the 3D view and see the Set Origin... sub-menu:


                    


Here you can find both the Origin to Geometry and two similar Origin to Center of Mass options.