BS = "British Subject" = either his father was British (mothers didn't count, at this period in time), or he had naturalised, or neither of the above is true and the census info is misleading/incorrect.
There is something very important regarding this last option in the General Report of the 1891 census, bolding mine:
Foreigners by nationality as well as birth
The English Census takes cognisance of birth-places, but not of nationalities, with this exception, that persons who, though born abroad, are yet British subjects are directed to state this fact on their schedules. This, however, they frequently neglect to do; and, consequently, the "persons born in foreign states and not declared to be British subjects" are doubtlessly in excess of the real number of those who arc foreigners both by birth and nationality. To remedy this, it was the practice in former censuses to have recourse to the aid of surnames; and the abstracting clerks were instructed to consider all persons born abroad in European countries, who had distinctly English surnames, to be British subjects, even if no statement to that effect was made on their schedules.
There are, however, clearly very grave objections to this proceeding. How is the clerk to decide what is a distinctly British name? There are many surnames common to, England and foreign countries; and, even when there is some slight difference of spelling between the English name and its foreign equivalent, this is very likely to disappear when the entry is transcribed by the enumerator; Muller to become Miller, Schmidt to become Smith.
It was, therefore, thought wiser in the present Census to discard altogether this unsatisfactory attempt at rectification, and to deal with. the returns as they were made to us leaving the responsibility upon those to whom it properly belonged, namely, the individuals who filled up the schedules.
So in 1871 and 1881, the "BS" added later could have been the work of an abstracting clerk (the fellow whose job it was to tot up the statistics) who considered "Joseph Hines" to be a British name. It does look to me like in 1871 it is also not part of the original birthplace.
The marriage certificate may give you more clues, particularly his address, and the witness names. People did tend to travel in groups so he might have had relatives or friends in London who he traveled with or who were there before he came.
