I understand that Bob somehow possessed Leland Palmer, but what exactly was he and what was his relationship to the Black Lodge? What was his origin?
From the Twin Peaks FAQ:
This is perhaps the greatest mystery/question of Twin Peaks, a source of endless debate, and an issue to which each viewer must attach their own interpretation and significance.
This much is given to us: BOB is a disembodied spirit capable of taking over a human being. After he takes over, he manipulates his human host to commit acts of sex and violence and 'feeds' upon the emotions this produces. He is connected in some manner with other spirits which appear in either or both of the Black Lodge and White Lodge. An entrance to the Black Lodge (shown as the red room) is in Glastonbury Grove in the woods outside of Twin Peaks. See questions E39 and E40 for more on the Lodges.
As I understand it, the black lodge and white lodge represents the "bad" and the "good", most deep human edges. The doppelganger (a surrogate in life) mention will create the idea of all of us being both, more close to the white or black lodge, but both in the end.
Twin peaks happen to be more influenced by the black lodge, as you can tell by their inhabitants.
Keeping this in mind, Bob is actually the summon representation of the sin and the black lodge head in twin peaks.
In a less philosophical matter, Bob is actually a technician (the actor), that appeared at the bottom of a shoot by chance. David Lynch (Twin Peaks' director) saw him and found it creepy as hell and he liked it, so he added him as "Bob" in the story to made the black lodge thing clearer.
The 2017 Season 3 Episode 8 would appear to show the origin of Bob: In 1945 New Mexico, the first atomic bomb is detonated. The camera slowly takes us inside the nuclear explosion where it seems the nuclear explosion has broken through or made a hole to some other dimension. There, floating in a void, a demonic figure (credited as "the Experiment") spews a stream of fluid;
This would appear to be the birth of the spirit Bob & his entry into earth. So he is a supernatural entity from the outset.