We've been using Crucible/Fisheye with Fogbugz nicely now for a while. We are also Perforce users, and the systems together are really good. (For sake of brevity, whenever I mention Crucible, assume I mean Fisheye too).
There's nothing too much to it really. In Crucible repository settings we set up a couple of "Linkers" that pattern match a Perforce checkin comment like "BugzID:1234" to turn it into the full Fogbugz URL. So within Crucible, you can just quickly jump to the FB case number. I use the same set of patterns as the FB/Perforce integration, so users don't have to do anything different.
We also have a couple of patterns that match up "changelist 1234" with the Crucible entry for that changelist, which makes hopping around submissions quite easy.
Beyond that we don't do anything else for integration, other than maybe reference Crucible info via URL from a FB case. There's probably a lot more we could do, and maybe I need to look at some docs for Kiln to find out what would be useful to us to try and replicate.
PS: Maybe this is the wrong place to say it :), but the support from the Crucible guys is truly excellent.