In the the late 19th Century, the British Prime Minister was Lord Salisbury - family name, Robert Cecil. 'Bob' is, of course, the short form of 'Robert'. He gave a variety of Government positions to his not-very-able nephew, Arthur Balfour. That gave rise to 'Bob's your uncle' - meaning something pretty easy.
Another possible source is from a phrase 'all is bob' meaning 'all is safe' or 'everything is well'.