Maybe is what's known as an adverb of certainty or adverb of probability - it's used to show how certain we are about something. Commonly used adverbs of probability are:
certainly - definitely - maybe - possibly
clearly - obviously - perhaps - probably
...and the position of the adverb in the sentence depends on the adverb being used.
In the case of maybe, it is most often placed at the beginning of a sentence (more specifically, at the beginning of a clause)
- Maybe I will be there.
- Maybe we’ll go out to eat tonight.
- If you are tired, then maybe it is time to go home.
In certain situations, maybe can be placed at the end of a sentence, for example, if we are making a suggestion which we are not very certain about.
A: My car won't start.
B: It could be the battery, maybe.
As mentioned in the comments, maybe can also be a sentence in itself, for example, if we wish to express uncertainty in response to a suggestion:
A: Would you like to have chicken curry for dinner?
B: Maybe.
...or if we agree that something is possible:
A: Do you think we can get to the movie theatre before 7:00?
B: Maybe.
Looking your two suggested sentences
- We maybe have a problem.
- Maybe we have a problem.
...it should take the form of maybe [clause], therefore
Maybe we have a problem.
...is the better choice.