Building credibility can start with something as simple as this: I say what's gonna happen, and then it happens. And then I say something else is gonna happen, and then it happens. And I keep doing that over and over and over . . . .
If you say, "I'm going to estimate how much it's going to cost to do this project, and when we can have it done by to the level of quality you want," and then you do it — I mean, I don't care if that's one day's worth of work. If you do that over and over, dude, you are on another level.
Merlin Mann touches on a core description of project management in Back to Work Episode #127. If you're not already listening to Back to Work regularly, change that because you should be.