Ah... Many times I have wanted to do this and I always wind up back on this article. If there is a better method I haven't found it yet. It does require you add a little non-semantic markup, but there are many cases when an extra div or className is required to get a specific styling effect and the only other method you can use is a table. When we get browser support for css 3 you'll get your vertical centering without extra markup.
Note: There are simple ways to get vertical centering if you know some heights in advance, if you are trying to center a single line of text, or in several other cases. If you have more details then throw them in because there may be a method that doesn't require browser hacks or non-semantic markup.