デフォルトのXPathは遅くて使い物にならない、と思ったらjaxenを試してみましょう。
jaxen: universal Java XPath engine
使い方はごく簡単です。
XPath xpath = new DOMXPath("/foo/bar");
List<?> nodes = xpath.selectNodes(document);
しかもこのjaxen、universalと謳っているだけあって扱えるのはデフォルトのDOMだけではありません。dom4j, JDOM, XOMを扱えます。使い方はみんな同じで、newするクラスが違うだけです。
ちなみにdom4jとXOMはXPathの処理でjaxenを呼んでいるようです(dom4jの実装は見てないですが)。
XOMでは
nu.xom.Node node;
Nodes nodes = node.query("/foo/bar");
このとき、jaxenのベースクラスを継承したクラスを使ってXPathの評価を行っています。
ちなみにMavenを使っている場合は、pom.xmlに
<dependency>
<groupId>jaxen</groupId>
<artifactId>jaxen</artifactId>
<version>1.1.1</version>
</dependency>
を追加すれば使用可能になります。