Literally, this means teacher,
and in Kyokushin it is automatically used with 3rd and 4th dan holders.
In other organisations, it is sometimes a conferred title, and comes in addition to the belt ranking. In some styles, there is even a further refinement to this title, Sensei-ho which essentially means “Sensei in training” and is often used to signify a probationary promotion. (A similar terminology and grade can be applied for shodan as well).
Sensei is however, also a general term of respect in Japanese for all teachers of skills, and not just in karate. It means something to the effect of “S/he who has gone there before me”, and is more along the lines of leading the way rather than instructing.
Consequently, people with shodan and nidan are often also called Sensei if they are the chief or only instructor(s) in a dojo.