I go with the simple answer. Works for me.
long startTime = System.currentTimeMillis();
doReallyLongThing();
long endTime = System.currentTimeMillis();
System.out.println("That took " + (endTime - startTime) + " milliseconds");
It works quite well. The resolution is obviously only to the millisecond, you can do better with System.nanoTime(). There are some limitations to both (operating system schedule slices, etc.) but this works pretty well.
Average across a couple of runs (the more the better) and you'll get a decent idea.