Is there a rule to explain why (in most dictionaries) words such as half-brother or half-sister are hyphenated while stepbrother or stepsister are not?
Compound words in English can be separated by a space (e.g. ice cream), a hyphen (your examples), or nothing (e.g. bestseller).
But, the step in stepbrother, etc. is unrelated to the English word step as in thing you put your foot on to move (from Wikipedia article Stepfamily:)
The earliest recorded use of the prefix step-, in the form steop-, is from an 8th-century glossary of Latin-Old English words meaning "orphan". Steopsunu is given for the Latin word filiaster and steopmoder for nouerca. Similar words recorded later in Old English include stepbairn, stepchild and stepfather. The words are used to denote a connection resulting from the remarriage of a widowed parent and are related to the word ástíeped meaning bereaved, with stepbairn and stepchild occasionally used simply as synonyms for orphan. Words such as stepbrother, stepniece and stepparent appeared much later and do not have any particular connotation of bereavement. Corresponding words in other Germanic languages include: Old High German stiuf- and Old Norse stjúp-.
So this is not really a compound word so much as a separate word or a prefix (e.g. like unknown, pregame, etc.)