http://github.com/chrsan/css-selectors/tree has a cool implementation of full CSS3 Selector support.

Yes, this is the same CSS selector support as you get in JQuery. Eat your heart out.

It comes with a org.w3c.dom implementation out-of-box.

I augmented it with a dom4j implementation (so I could mixin tagsoup for real-world HTML).

It's slow as a dog compared with native xpath or regex, but its still cool nonetheless.

Update: OK, I was wrong about performance. My initial dom4j implementation was slow BECAUSE of xpath actually. When I changed it to use dom4j node traversal methods, performance increased by over 50x. I'm happy with performance now.