Here, the adjective foggy means hazy, vague.
The earliest occurrence of the phrase that I have found is from a correspondence, by a person signing themself ‘Le Diable Boiteux’ (i.e., ‘The Lame Devil’), published in The Times of India (Bombay, Maharashtra, India) of Monday 4th May 1863:
(From our own Correspondents.)
NORTH-WESTERN PROVINCES, 24th April.
I have been stirring lately in order to be present at the several tumashas 1 of Monday last. For days previous, all over my territories, ricketty erections of split bamboo, bearing a much nearer resemblance to pea-rods than to anything triumphal, lined and obstructed the roads and streets of the various stations, while here and there a structure spanned the road which would have driven the soul of Inigo Jones 2 into fits, had it been there to see. Yet, with the slender means at their command, it is wonderful how well the natives manage to light up at night! And with what a will they do it too; one half of them, I daresay, not having the foggiest idea of what or who they were illumining for.
1 The noun tamasha (also formerly spelt tomashaw, tumasha, etc.) denotes an entertainment, show, display, public function.
2 Inigo Jones (1573-1652) was the first notable English architect, responsible for introducing the classical architecture of Rome and the Italian Renaissance to Britain.
The second-earliest occurrence of the phrase that I have found is from the North British Daily Mail (Glasgow, Lanarkshire, Scotland) of Friday 7th September 1866:
Hobble-de-hoy cannot be left with his hands idle, and Latin and Greek form a very good outlet for his energies. […] The consequence is, that many youths who have really no time to spare, whose parents are not sufficiently well off to afford them that luxury, are, when barely able to read their own language, set to work at a tongue or two tongues, of which they can never expact [sic] to have the foggiest idea.
The earliest occurrence that I have found of the shorter phrase not to have the foggiest (i.e., with ellipsis of idea, notion, etc.) is from Sailors—Simple and Otherwise, by Rose Henniker Heaton, published in The Westminster Gazette (London, England) of Saturday 18th January 1913—however, cf. footnote:
It is the shallowest platitude to say a sailor is recognisable by his keen, clear-cut face, his square shoulders and alert manner. Should all these be hidden under cover of night his tongue would betray his calling the first moment he opened his mouth. For example: An express train was running through a long tunnel, black as the proverbial Egyptian night. “Can anyone tell me where we are now?” asked an anxious voice. “I haven’t the foggiest,” came the reply out of the darkness, leaving no one in doubt as to the speaker’s familiarity with manœuvres, night attacks, and the like.
The second-earliest occurrence that I have found of the shorter phrase is from the caption to this cartoon by Arthur Wallis Mills (1878-1940), published in Punch, or the London Charivari (London, England) of Wednesday 22nd August 1917:
Uncle. “By Jove, there’s a nice quiet-looking girl just come in. Wonder who she is.”
Niece. “Haven’t the foggiest. Must be pre-war.”
Note: But the ellipsis of idea occurs earlier in the following answer, as transcribed in the account of a meeting of the Dulverton Rural Council, published in The Devon and Exeter Gazette (Exeter, Devon, England) of Friday 2nd September 1910:
The Chairman: It [= the improvement to the road] ought to have been done six months ago.
The Clerk: Quite right. I wonder when they are going to begin the work.
Mr. Tapp: Have you any idea?
The Clerk: Not the foggiest.