There are various ways to go about this, depending on why you are doing it. The first two are "officially supported" by most window managers and described in specs, and then it descends into fragile hacks.
Semantic
The specs encourage you to use _NET_WM_WINDOW_TYPE rather than setting the position, if it makes sense to do so. See http://standards.freedesktop.org/wm-spec/wm-spec-1.3.html#id2507144
For example, a DIALOG type (or a window with the WM_TRANSIENT_FOR hint set) will usually be centered on its parent window or on the screen, and the _NET_WM_WINDOW_TYPE_SPLASH (splashscreen) type will usually be centered on the screen. "Usually" here means "sensible window managers probably center it, and people using weird window managers are not your problem, let them suffer."
(Another hint along the same lines, though not what you want here, is _NET_WM_STATE_FULLSCREEN, which avoids manually sizing/positioning in order to be fullscreen.)
If semantic hints work, the window manager code to handle the positioning is hopefully smarter than anything one can easily code by hand, for example it might deal with multihead setups. Setting the proper semantic type may also allow the WM to be smart in other ways, beyond positioning.
Gravity
If there's no semantic hint in the specs that helps you, then you can center by hand. It's important to note that window managers are allowed to ignore a manual position request and some of them will. Some may only honor the request if you set the USPosition flag in WM_NORMAL_HINTS (this flag is supposed to be set only if the user explicitly requested the position, for example with a -geometry command line option). Others may ignore the request always. But, you can probably ignore WMs that do this; the user chose to use that WM.
The way you compensate for the window decorations (the titlebar, etc.) is to use the win_gravity field of WM_NORMAL_HINTS, which is originally in the ICCCM (see http://tronche.com/gui/x/icccm/sec-4.html#s-4.1.2.3) but better-specified in an implementation note in the EWMH: http://standards.freedesktop.org/wm-spec/latest/ar01s09.html#id2570420
For WM_NORMAL_HINTS see http://tronche.com/gui/x/xlib/ICC/client-to-window-manager/wm-normal-hints.html#XSizeHints (note: the type of the property is WM_SIZE_HINTS and the name of the property is WM_NORMAL_HINTS, so there are two different atom names involved).
To center, you would set the win_gravity to Center, which allows you to position the center of the window (including its decorations) instead of the top-left corner.
win_gravity is not often used and is likely to be buggy in some window managers because nobody bothered to code/test it, but it should work in the more mainstream ones.
Update, possible confusion point: There are other "gravities" in the X protocol, specifically the CreateWindow request lets you set a "bit_gravity" and "win_gravity"; these are different from the XSizeHints.win_gravity. The CreateWindow gravities describe how the contents (pixels/subwindows) of a window are handled when the window is resized.
Hacks based on guessing decoration size
It's a fragile hack, but... you can try to figure out the decoration size and then incorporate that into your positioning.
To get the size of the window decorations, one way is the _NET_FRAME_EXTENTS hint, see http://standards.freedesktop.org/wm-spec/latest/ar01s05.html#id2569862
For older-school window managers (but not the fancy new compositing ones, though those hopefully support _NET_FRAME_EXTENTS) the window decorations are an X window, so you can get your parent window and look at its size.
The problem with both of these approaches is that you have to map the window before the decorations are added, so you have to map; wait to get the MapNotify event; then get the decoration size; then move the window. This will unfortunately cause user-visible flicker (the window will initially appear and then move). I don't think there's a way to get the window decoration size without mapping first.
Descending further into the realm of awful hacks, you could assume that for windows after the first one you map, the decorations will match previously-mapped windows. (Not that this is a sound assumption: different kinds of windows may have different decorations.)
Implementation note: keep in mind that the decoration window can be destroyed at any time, which would cause an X error in any outstanding Xlib requests you have that mention that window and by default exit your program. To avoid this, set the X error handler when touching windows that don't belong to your client.
Override redirect
Using override redirect is a kind of bazooka with bad side effects, and not at all a good idea if your goal is just to center a window.
If you set the override redirect flag when creating a window, then the window manager won't manage its size, position, stacking order, decorations, or map state (the window manager's redirection of ConfigureRequest and MapRequest is overridden).
This is a really bad idea for anything the user would think of as a window. It's usually used for tooltips and popup menus. If you set override redirect on a window, then all the normal window management UI will be broken, the stacking order will end up basically random (the window will tend to get stuck on top or on bottom, or worse get in an infinite-loop restack fight with another client).
But, the override-redirected window won't have decorations or be touched by the WM, so you can surefire center it with no interference.
(If you just want no decorations, use a semantic type like SPLASH or use the "MWM" hints, don't use override redirect.)
Summary
The short answer is set the semantic hint if any is applicable, and otherwise use XSizeHints.win_gravity=Center.
You can kind of see why people use toolkits and SDL ;-) lots of weird historical baggage and corner cases in the client-to-window-manager interaction generally, setting window positions is just the beginning of the excitement!
XMoveWindow
on the client area, but you can adjust for the decorations size. – Vallecula