Does 'soha' always need to be followed by the word 'nem'?
Short answer: yes.
"Sohasem" means the same.
In imperative we use the word "ne" instead of "nem": Soha ne mondd, hogy soha! = Never say never.
As an exclamation you can use it on it's own: Soha! = Never!
You might encounter sentences where there are other words between "soha" and "nem", but sooner or later there has to be a "nem" after "soha".
There are of course some exceptions, like the phrases "most vagy soha" meaning "now or never", or "soha jobban" ("never better").
Also in case of "van" ("is/have") you do not need "nem", because in Hungarian there is no "nem van", but you use "nincs", e.g. "soha nincs rám ideje" - "he never has time for me".
Also "nem" may appear before "soha": "soha nem lesz vége" is actually same as "nem lesz vége soha" meaning "it will never end". It depends whether you want to emphasize no or never.
There are also some really rare cases when you can leave "nem", mostly for rhetorical reasons. One might use without it when it comes to never was or we have not seen ever, but IRL you face that once in a decade. ("Soha olyan vérszopó hiénát, mint...")
Update: I found out, that according to spelling rules (helyesírás), soha nem is written as two words, but sohasem is written as one.
It is because there is a slight difference between soha [...] nem and sohasem. The last one also translates to "never ever". As such phrase it became one word in Hungarian.
Thank you all who have responded. I could never have imagined that this question could be so deep!!!
Actually in Hungarian every question might become deep. It is very difficult because of all those exceptions over the rules. Even if you are a native speaker you are not aware (or do not think) of all of them, unless you are a true grammar teacher or an academic :)
Keep on going with your journey, it is a beautiful language and I guess we all appreciate your enthusiasm to be part of it :)
I'm most definitely not going to give up but I will need help along the way! :)
It should be mentioned that in Hungarian double negative is used. E.g.:
I did not see anyone.
I saw no one.
Nem láttam senkit.
There wasn't anyone in the streets.
There was no one in the streets.
Nem volt senki az utcán.
I don't know anything about Jenny.
I know nothing about Jenny.
Semmit nem tudok Jennyről.
I didn't go anywhere at the weekend.
I went nowhere at the weekend.
Sehová sem mentem a hétvégén.
Never look for logic in languages!
Logikát sohase keress a nyelvekben!