There are a couple of ways to do profiling. One way is to add instrumentation at compile time. This has the disadvantage of requiring a special compile and flag for instrumentation. It can also have a fairly high overhead cost and can get in the way of what you are trying to measure. There are several university projects out on the web that do this kind of profiling. Another approach, is a time sampling approach. At some increment of time, the program can be stopped and looked at and then restarted. This would of course slow it down quite a bit, so generally it is not stopped, but looked at from another process. This lets the program behave pretty much like it would if it were not being sampled. This too is not without it's problems. If the sampling rate is too high, then you can get a ton of data and fill up your disk. If it is too low, then you might not see some things that are of interest.
Dan (djo35) has suggested a couple of possible approaches. I have to say that I am sort of old fashion too and use print statements a lot. That said, I don't recommend it for trying to find races conditions. The main issue with parallel programming is timing. I have looked at programs (that I didn't write) that have run for years "correctly" that "all the sudden failed". The problem was a race condition that had gone undetected for all that time. Using a good tool for finding race conditions and profiling is essential. It can reduce your development time and number of problems substantially.
That said, I am afraid that I am not in the position to recommend compilers or tools. I work for Sun Microsystems and we produce compilers, performance libraries, profiling tools, and threading tools that I would love to have you try. They work on Solaris and some versions of Linux (and we are trying to increase the Linux versions our code works on). The code is free and you can get a support contract if you want to. However, these tools may or may not be what you need and what I am trying to do here is answer questions about OpenMP and not push any particular vendor products. So all I can say, is look at the OpenMP web site and the compunity web site for links to various tools; check Yahoo, Goggle, or whatever your favorite search tool is for keywords like OpenMP and profiling and see what you get; and keep checking back to see if someone else has added any more suggestions here.