In 1803 Kirill Khlebnikov, an agent of the Russian American Company, was imprisoned for three months in Petropavlosk, Kamchatka by Major General Koshelev, administrator of the district. The reason was Khlebnikov's refusal to raise prices on Company goods to line the pockets of Koshelev and his cronies. (The Khlebnikov Archive, Unpublished Journal 1800-1837, The Rasmuson Library Historical Translation Series, Vol 5). In what type of structure would he have been held? What would have been the conditions?
Khlebnikov's journal, in the volume you mentioned, has him arriving in Nizhne-Kamchatsk ten days before his arrest, and staying there after his release. I don't see any evidence that this transpired in Petropavlovsk, which was not the capital of Kamchatka until a decade later.
Nizhne-Kamchatsk was an ostrog, a wooden palisade fort. The word ostrog also indicates a prison in that fort. Typically an ostrog had one or more towers for defense. Including people living outside the fort, in 1792 the settlement had 548 residents. You can see both in this illustration from Krasheninnikov's 1755 work:
I can only imagine that the prison was inside the fort. It would have been a wooden building, possibly sharing a wall with the fort itself, and possibly the ground floor of a tower. The fort shown is a different one, but illustrates the type of construction involved:
Food was scarce in all of Kamchatka, and often rotted on the way there. While Koselev devoted a lot of resources to developing agriculture, it did not work well even in the more favorable Kamchatka River valley. Foraging roots, berries, and grasses was a major part of locals' diets, but the single most significant ingredient was salmon, eaten during most of the year as jerky, yukola. Probably the prisoners were fed a starvation diet.
Possibly, while Khlebnikov was imprisoned, he was forced to work in the local saltworks. In 1794 it was operated by twenty men, probably exiled prisoners guarded and goaded by soldiers of the ostrog. Imprisonment in mainland Siberia was more practical, so most exiles were sent there instead.
In 1807, Khlebnikov and Koselev spent a day together in Ichinsk.
My primary source for this answer was James R. Gibson's "Feeding the Russian Fur Trade".
In America there existed the word "fort", that had got the meanings "fortified outpost" - for frontier and "small fortress" - for use in usual warfare.
In Russian frontier the word for "fortified outpost", was "ostrog". Later often towns appeared around that old centre, such as Petropavlosk, mentioned by you. And the old fort was used there as a prison. So, the name "ostrog" became one of synonyms for "prison".
These forts could be very beautiful
You can see many images of different ostrogs here.
It is hard to find that very ostrog picture. There are many pictures of other ostrogs, but the only old picture of the Petropavlovsk in 18th Cent that I have found after half an hour of looking is here:
Surely, it looked differently in 19 Cent, but Petropavlovsk was considered extremely important in strategic sense and obviously, no drawing was permitted.
There is a problem with searching itself, too, for Google provides the must more known Petropavlovskaya fortress in St. Petersburg instead. And castle "Ostrog" in the Czech republic. Don't even try to look in English.
So, as for the question "where" - the answer is clear - your hero was hold in ostrog.
As it looked from inside and conditions - that depended on the concrete prisoner, crime and situation. Some prisoners lived in a room or even a hole dug in the ground, having only bad soup and a piece of bread for a day, some important prisoner could have a good room near the mayors premises, having dinner with him and be only forbidden to go out of the ostrog, or even without that limit.