Step brother and half brother appear to mean one and the same thing. Please refer to the following link:

http://wordnet.princeton.edu/perl/webwn?s=half brother

--------------------------------------------------
Note added at 8 mins (2006-06-26 15:07:39 GMT)
--------------------------------------------------

सौतेला भाई या सौतेली बहन

--------------------------------------------------
Note added at 13 mins (2006-06-26 15:12:23 GMT)
--------------------------------------------------

Half brother means

brother with one parent in common: a son of one of your parents by a different partner

http://encarta.msn.com/encnet/features/dictionary/Dictionary...

So sautelA bhAi is a suitable term in this case.

--------------------------------------------------
Note added at 1 hr (2006-06-26 16:16:33 GMT)
--------------------------------------------------

Reference: Your noted below:

Hindi does not have separate words for Step Brother and Half Brother. It has sautelA bhAi for both of them. We can't translate it as AdhA bhAi. It should be sautelA bhAi.

--------------------------------------------------
Note added at 1 hr (2006-06-26 16:19:53 GMT)
--------------------------------------------------

typo: pls read 'your note below' in place of 'your noted below'

PC and other dictionaries are right. Hindi has only सौतेला भाई for step brother because till now the said "Half" concept belongs to West. Divorce and remarriage happens so frequently there (don't bother, we are also advancing to that stage!) that the old word "step brother/sister" has lost its relevancy. "Half brother/sister" is a new word in English which indicates a new family concept. There is a blood relation anyway with step brother/sister but there is no blood relation with Half brother/sister. They are children of previous marriage of step father or step mother.
In this situation, a new hindi word should be discovered because this type of family relation also evolves in our country gradually.
I suggest a word : ansh bhaai/ ansh bahan अंश भाई / अंश बहन।
you do not find the word in any dictionary. लेकिन क्या करें- ऐसे सम्पर्क के बारे में वे सोचे ही नहीं!!

Though I agree with Keshab, Langclinic, but still this term is interesting, so I am trying to bring few new terms!
Bhai is also know as 'Sahodar' (Birth from same 'Udar') so 'Annyodar' is coined, Similarly taking clue from Ardhnareshwar Avtaar, Ardhansh Bhai is coined. Now peers and asker may have choice!