Histogram is the best way to judge.
How are you shooting? If you're shooting in JPEG, you should check your camera settings to see if you have the brightness turned up or contrast down or something strange like that.
Assuming you're shooting in raw and opening the files in something like lightroom, then you're probably actually overexposing.
Because the image on your camera screen is corrected, the histogram is the only way to judge because it's the only way to see the full dynamic range your camera captured.
The histogram displays, as a graph of dark to light, the amount of information in your photo. The higher the graph, the more information you have at that brightness level.
As a result, for an evenly lit scene, you want your histogram to be a bell curve with the peak centered in the middle. This means that the majority of the data in the photo is recorded roughly at your camera's best recording levels, with best dynamic range around the scene.
However, the most important thing to watch for is big bars on the sides of your histogram. This represents "clipped" data, data that is too bright or dark to be recorded.
If your histogram is roughly centered, without bars on either side, you can shape the photo however you want in post-processing and it should open at the right brightness level.
There are cases (such as a backlit subject) or a subject in a spotlight) where you want that subject and only that subject to be recorded, so your histogram will be skewed bright or dark because the part you care about is a small portion of the whole image.
For the most part though, try to keep the histogram centered.