It's established in the script that Sisko and O'Brien are exploring systems close to the wormhole (e.g. rather than through it).
SISKO (V.O.): Station log, Stardate 47573.1. We're getting more and
more requests for information about setting up colonies in sectors
close to the wormhole. So, Chief O'Brien and I have set out to survey
near-by star systems for M-Class planets.
...
SISKO: It's M-Class all right. One hundred and sixty million kilometers from Orellius Minor. Should be a perfect place to set up a colony...
DS9: Paradise - Original Screenplay
And while it's not made abundantly clear in the episode that they're on the Alpha Quadrant side, the additional materials provided (the Star Trek Star Charts factbook and the official StarTrek.com Databank) leave no room for interpretation whatsoever.
Orellius Minor: Name for an F-type star in Sector 401 -- adjacent to the Bajoran sector -- and its major, Class M world orbiting at 160 million km. The previously unscouted planet is found to host a human colony, led by an idealistic but single- minded opponent of technology who kept Commander Sisko and Chief O'Brien captive until they escaped in 2370.
http://www.startrek.com/database_article/orellius-minor