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.
There are other four key shortcuts too, e.g. `Ctrl Shift Alt M`.. :P Anyway, I edited your answer, feel free to rollback if you disagree with my edits.
Oh, nice; But I looked through the user preferences and found no such shortcut
Sometimes neither of these two is sufficient; in that case in edit mode select whole object (`A`), `G`rab it, move it to such a location that the desired center is at 0,0,0. Then in Object mode set 3D cursor coords to 0,0,0 and then `Ctrl Alt Shift C`, Origin to 3D Cursor.
@SF. What do you mean by not sufficient? If you want to position the origin, then you can use the 3D cursor, but otherwise, I don't get what you mean.
@someonewithpc: Just recently, I had a part that was a tube 3 meters long, hollowed out one meter deep through one end. I needed the origin squat in the middle of its length. Center of mass would shift the origin towards the full end where most of mass is concentrated. Center of geometry would gravitate towards the bunch of vertices of the bore hole (versus the "plain" full end). Putting the cursor 1.5m from one end did the trick.