The book Science Fiction and Science Fact has a "black hole" entry (an expanded version of this entry from the Science Fiction Encyclopedia online) which mentions a few early examples of stories that seem to anticipate things similar to a black hole:
The idea of black holes had been vaguely anticipated in such
constructs as the Hole in Space in Frank K. Kelly's "Starship
Invincible" (1935), the hole created by the matter-annihilating giant
positron in Nathan Schachner's "Negative Space" (1938), the the Pit
generated by a collapsing star in Harry Walton's "Below—Absolute!"
(1938). Fred Saberhagen's "The Face of the Deep" (1966) described the
concept in detail ahead of the term's coinage.
I found Harry Walton's "Below—Absolute!" in a DVD-R collection of old Astounding Science Fiction magazines from this eBay seller. It's an interesting example of a fictional object which anticipates a number of features of black holes, even though the story was published in 1938, whereas the histories here and here say that the first suggestion in the physics literature that a massive star might collapse to the size of the Schwarzchild radius (the point at which we would now say that a black hole forms, with the Schwarzschild radius being the location of the black hole's event horizon) was made in 1939. In this story, some meteor miners find a "sheer vacuum of non-spatial darkness", a "nothingness made tangible, a canyon of blackness in which the stars were lost", whose "outline against the tapestry of stars was that of an enormous, perfectly circular disk". They call it "the Pit", and soon they receive psychic communications from an entity that exists in another universe--what it calls an "other-space"--connected to our universe by the Pit, which the entity calls "the Passage". The entity explains that the Passage is "an artificial rupture of the space-time continuums involved, which we were enabled to bring about by taking advantage of a rare cosmic occurrence—a super-nova, or exploding star, that simultaneously ruptured your space at a point which now marks the opposite end of the Passage." So even though the author was writing before any physicists seriously suggested a real star could collapse to the Schwarzschild radius, it's possible he was aware of the Schwarzschild metric which would later come to be understood as the mathematical description of a non-rotating black hole, or of cases where physicists had brought up the issue of a star collapsing this far only to dismiss it as an impossibility, like this comment by astronomer/physicist Arthur Eddington on p. 6 of The Internal Constitution of the Stars from 1926:
A star of 250 million km. radius could not possibly have so high a
density as the sun. Firstly, the force of gravitation would be so
great that light would be unable to escape from it, the rays falling
back to the star like a stone to the earth. Secondly, the red shift of
the spectral lines would be so great that the spectrum would be
shifted out of existence. Thirdly, the mass would produce so much
curvature of the space-time metric that space would close up around
the star, leaving us outside (i.e., nowhere).
So depending on whether you think Harry Walton should be counted as describing a black hole or just inventing a fictional object which coincidentally had some properties similar to a black hole, his story could be an early example of a black hole as a portal to another universe.
Another possible early black hole story mentioned in the Science Fiction and Science Fact quote above was "The Face of the Deep" from 1966, which is available online here here, but reading it I'm not sure it's correct to say that it "described the concept in detail"--it talks about "a hypermassive sun a billion times the weight of Sol", but without suggesting that it lacks a material surface like other stars. Perhaps the author of the Science Fiction and Science Fact article was thinking of the comments about the object's "horizon", but what it refers to in the story is a "terrible horizon of the hypermass's shroud of dust", whereas a black hole event horizon not made of any matter but is just a boundary in spacetime between places where it's possible to escape the black hole and places where it's not. It is possible however that the author was thinking in terms of the "frozen star" picture of a black hole discussed here ('Now, this led early on to an image of a black hole as a strange sort of suspended-animation object, a "frozen star" with immobilized falling debris and gedankenexperiment astronauts hanging above it in eternally slowing precipitation'). According to p. 4 of Black Hole Physics, "The names 'frozen' or 'collapsed' stars [was] used by specialists until the end of the sixties", which would fit "The Face of the Deep"'s 1966 publication date. In any case, this story doesn't involve falling in or traveling to another universe or time.
The entry also mentions an early story, "He Fell into a Dark Hole" by Jerry Pournelle from 1972, whose wikipedia entry indicates it's an early example of traveling through space via a trip through a black hole (though not through time or into alternate universes):
Ward develops a theory that can allow the Daniel Webster and the
survivors to jump out of the system. However, the plan requires a
spaceship to go into the black hole. Harriman volunteers and
successfully pilots one of the crippled ships into the black hole. The
theory works, and allows the survivors to escape to the nearest star.
The entry also mentions another early example of black-hole-inspired shortcuts through space, also from 1972: George R. R. Martin's "The Second Kind of Loneliness". This story does not actually use the term black hole, but the idea seems at least loosely inspired by them:
The ring turned silent beneath me, its far side stretching away into
noth-ingness. I touched a switch on my console. Below me, the
nullspace en-gines woke.
In the center of the ring, a new star was born.
It was a tiny dot amid the dark at first. Green today, bright green.
But not always, and not for long. Null-space has many colors.
I could see the far side of the ring then, if I'd wanted to. It was
glowing with a light of its own. Alive and awake, the nullspace
engines were pouring unimaginable amounts of energy inward, to rip
wide a hole in space itself.
The hole had been there long be-fore Cerberus, long before man. Men
found it, quite by accident, when they reached Pluto. They built the
ring around it. Later they found two other holes, and built other star
The holes were small, too small. But they could be enlarged.
Temporarily, at the expense of vast amounts of power, they could be
ripped open. Raw energy could be pumped through that tiny, unseen hole
in the universe until the placid surface of nullspace roiled and
lashed back, and the nullspace vortex formed.
On page 372 of the book Time Machines by Paul Nahin, there's a description of the 1934 story "Sidewise in Time" by Murray Leinster which seems to describe something like a black hole, and includes the idea that things that fell into them would not "cease to exist" but would "cease to exist in our space and time", suggesting they end up in some other "space and time", so this could be an early example of black holes as portals to another universe:
This is primarily a parallel-universe story, about which more is said
in Chapter Four, but near its conclusion in the obligatory
genius-explains-it-all dénoument, we read, "We know that gravity warps
space....We can calculate the mass necessary to warp space so that it
will close in completely, making a closed universe....We know, for
example, that if two gigantic star masses of certain mass were to
combine...they would simply vanish. But they would not cease to exist.
They would merely cease to exist in our space and time." As another
character sums it up, "Like crawling into a hole and pulling the hole
in after you."
As with Harry Walton's "Below—Absolute!" discussed above, it's not clear to what extent if any this author was aware of real theoretical work concerning what we now call black holes, though the comment that "gravity warps space" indicates he was at least familiar with the theory of general relativity which is used to describe black holes.
It's worth noting that the idea of using a black hole to travel to other universes actually has some basis in theoretical physics--the "maximally extended" spacetime for an idealized eternal rotating black hole has a singularity that travelers can potentially avoid falling into, and instead steer in such a way that they exit a white hole in a region of spacetime unreachable from our own except through the black hole/white hole connection. The "Inside Black Holes" website by physicist Andrew Hamilton contains a diagram of this on the Penrose diagrams page, scroll down to the bottom diagram of a "Kerr black hole" which is the idealized rotating black hole solution I mentioned. Another interesting feature of the theoretical model is that there is an interior region where closed timelike curves are possible, i.e. time travel (a fact mentioned in the bottom section of this page from the "Inside Black Holes" site, and also on p. 144 of the book The Story of Collapsing Stars, viewable on google books here). Physicists don't really think this is realistic since unlike the idealized solution which is eternal and unchanging, a realistic rotating black hole would form from collapsing matter and physicists think such a black hole would probably have a different type of singularity which cannot be avoided, so that there is not actually any path through the black hole that connects to the interior of a white hole (I gave some details in a physics stack exchange answer here). Still, the black hole/white hole solution probably inspired a lot of science fiction speculations about travel to other dimensions/universes--the Science Fiction and Science Fact entry says:
Such hypotheses led to the further elaboration of the basic idea into
that of a "wormhole": a metaspatial tunnel connecting a black hole
with a complementary "white hole", which could operate as a
faster-than-light transport mechanism or a means of interuniversal
travel. The popularisation of the notion was assisted by John
Gribbin's White Holes: Cosmic Gushers in the Universe (1977) and
Adrian Berry's The Iron Sun: Crossing the Universe Through Black
Wormholes became the most fashionable mode of interstellar travel in
the last decades of the twentieth century, notably deployed in such
novels as Paul Preuss' The Gates of Heaven (1980), Robert J.
Sawyer's Starplex (1996), and Iain M. Banks' The Algebraist (2004).
They also function as doorways through time, as in Preuss' Re-Entry
(1981) and Stephen Baxter's Timelike Infinity (1992) and "The
Gravity Mine" (2000).
The wikipedia entry for Black holes in fiction mentions that Preuss' The Gates of Heaven and its sequel Re-Entry (1981) do establish that the black hole connects to another universe rather than just another location in our universe. Depending on whether this is mentioned in the first book or only in the second, perhaps an earlier example of inter-universe travel would be this 1980 comic adaptation of the 1979 Disney Movie "The Black Hole", which Richard posted in a comment on this question (this may also have been the intent of the movie-makers, but it wasn't very clear what happened at the end of the movie). And "Sidewise in Time" from 1934 which I mentioned earlier may be a much earlier example where the idea of traveling to another universe by a black hole is at least mentioned, even if it doesn't happen in the story (though as I said it's not clear whether the author was aware of real theoretical models of black holes, or was just inventing his own fictional science based on vague knowledge of gravity curving space in general relativity). As for time travel, I haven't found any examples earlier than user14111's answer of Niven's "Singularities Make Me Nervous".
As I said above though, I think the real origin of this trope of going into a black hole and exiting in a completely different region of spacetime would be actual theoretical models dreamed up by physicists (from looking around online, I think both this idea and the idea of closed timelike curves in the interior of a rotating black hole trace back to the paper "Global Structure of the Kerr Family of Gravitational Fields" by Brandon Carter, from 1968), which inspired later science fiction writers to make use of the idea.