Sometimes, when I think of genre fiction (such as horror, fantasy, science fiction, and the like) and historical fiction, it's hard to tell the difference between the two.
There are superficial differences, certainly. You won't find me claiming, say, that a novel about a captain of a ship in the Napoleonic Wars and a novel about a family living alongside fairies have much in common stylistically, thematically, or in terms of plot. On those levels, they're probably about as wildly different as different can be. But this is sort of like saying that a city bus and an airplane have different engines and fuels and aerodynamics. While these are all obviously true, the bus and the plane still have the same function: to take people somewhere else.
Which is what both genre fiction and historical fiction are meant to do — when the reader picks them up and begins to turn pages, the first thing they expect to see is a lot of world-building going on. For both forms of fiction, the reader wants to be taken from wherever they are and find sights and smells and cities entirely new to them, with innovative languages and slang and strange factions with surprising intentions. They want to experience an extraordinary place with new and unfamiliar rules, with customs and habits and codes of conduct that are entirely foreign to them. They want to sip drinks of odd colors and sometimes questionable manufacture, taste foods they've never imagined, or possibly see things that they've never imagined could be food being eaten with enthusiasm. And many readers of genre and historical fiction will definitely expect a new geography. After all, which novels come with more maps in the front than those of historical, fantasy, or science fiction?
Of course, there is one key difference. The worlds described in historical fiction have, as best as we can figure, actually happened. Once upon a time, they actually were. To correctly bring them to life, authors of historical fiction must be warriors of research, roving through libraries and hunting down interviews with experts or, preferably, people who actually experienced that era first-hand, should it be recent enough. And there is always the drive to find that fact or angle on history that's utterly surprising to the reader, the one that subverts every previous notion they had and makes them gasp with astonishment, "How amazing it is to find out it was really like that!" I recall reading Michael Crichton's Timeline and being surprised at the relaxed social aspect of medieval castles during peacetime, or how average peasants had access to metal jewelry. 
And Bernard Cornwell's account of longbow training in Harlequin utterly fascinated me in how difficult it was, which I hadn't expected. These may be the curiosities that so strongly attract us to historical fiction. Depending on the subject, finding these facts can be either difficult or easy, but at the end of the day the author has plenty of documented resources to draw from when creating their worlds. How much they adhere to these historical elements is up to them, depending on the story they're telling, though this carries its own dangers. Too much, and the story's as dry as, well, a history book. Conversely, a certain amount of deviation is expected, but I've seen Prince Albert turn out to be Jack the Ripper a number of times.
When it comes to believable world-building, genre writers are either in luck or completely screwed. They have the luxury of being able to make up whatever they want, but the bad side is that they can really make up whatever they want. Going overboard is all too easy, and readers have an uncanny nose for contradictions, or just overly-whimsical silliness. If the world the author creates is too exotic, too impossible, or too outlandish, the reader can't establish sympathy, and so has no reason to follow along. You can see this effect in science fiction television — how many shows set in space have people in suits and ties and familiar military uniforms? The reason behind this is that it's tough to take a guy in robes and a three-foot headdress that seriously, no matter what he's saying, so they take an average suit and give it a bizarre cut and call it a day instead. And genre authors are going to have a lot of explaining to do in their worlds, from the function of True Names in Ursula K. Le Guin's Earthsea to the scientific marvels that populate sci-fi so densely, which just provides more opportunities to ruin the suspension of disbelief. People are going to want to know how the spaceship traverses such extreme distances, even if it does involve Unobtanium. When writing about conventional ships with sails, as one would in historical fiction, it's safe to assume the reader has heard of wind.
So there's definitely a balancing act there for both forms. In historical fiction, the reader wants a world full of historical details, preferably of the rich and astonishing sort, but the story must not adhere too closely to them, which can hobble or slow it, or stray too far from them, which violates the "historical" part of "historical fiction." Similarly, when picking up genre fiction readers expect something fantastic and alien, but if it's too fantastic and alien then there's just no reason to keep going.
When I started writing Mr. Shivers, my historical horror novel, I knew I wanted to use the historical aspect as a jumping-off point, and then do something else entirely. I wanted to start with a place already well-known to us all, something established in Western consciousness, and then slowly start to remove it, pulling the setting down brick by brick until the reader was somewhere they never expected to be at all. The characters experience the same thing as the reader — though they begin in the Dust Bowl of the Great Depression, with each step west they find themselves somewhere much harsher, much more primal, and very old. And by the time they realize what's happening, they've already changed themselves.
In fact, it's perfectly possible to interpret the story as a series of perversions: for the general populace in the story, the economy and the world as they knew it has been perverted into something desperate and rootless. For the reader, this recognizable, familiar version of the Great Depression is perverted until it's a horrifying and fantastic place, very different from the historical setting we began with. And for the characters, who begin with the noblest intentions, they find themselves scarred and warped by their journey until they're something quite different on the other side. And somewhere amid all this is a scarred man in a gray coat, known by the hobos and the freighthoppers only as Mr. Shivers, who is driving all these perversions along, tearing down recognizable signs of civilization as he goes and leading the characters and the reader further into the savage reaches of the west.
Perhaps what I wrote is not about world-building, of either the historical or genre sort. Maybe, deep down, it's about the very opposite. Maybe that's why it doesn't come with a map.