An archived version of the Galactic Empire article on starwars.com notes that
The Imperial starfleet of Star Destroyers and TIE fighters maintained order in the galaxy.
The Imperial Starfleet is estimated to consist of 25,000 Star Destroyers. Most of these Star Destroyers were Imperial-class, but the Imperial Starfleet also included even larger Star Dreadnoughts such as Executor (which participated in the Battles of Hoth and Endor).
The Imperial Starfleet's involvement (along with the Imperial Army's) in putting the Rebellion on the run despite the loss of the Death Star is supported by the opening crawl for Episode V:
It is a dark time for the
Rebellion. Although the Death
Star has been destroyed,
Imperial troops have driven the
Rebel forces from their hidden
base and pursued them across
the galaxy.
Evading the dreaded Imperial
Starfleet, a group of freedom
fighters led by Luke Skywalker
has established a new secret
base on the remote ice world
of Hoth.
The evil lord Darth Vader,
obsessed with finding young
Skywalker, has dispatched
thousands of remote probes into
the far reaches of space....
If the Rebels are on the run, the implication is that the Empire is able to maintain control for the most part.
The statement in Episode IV you are referring to reflects the opinion of Tarkin:
Tarkin: The Imperial Senate will no longer be of any concern to us. I've just received word that the Emperor has dissolved the council permanently. The last remnants of the Old Republic have been swept away.
Tagge: That's impossible! How will the Emperor maintain control without the bureaucracy?
Tarkin: The regional governors now have direct control over territories. Fear will keep the local systems in line. Fear of this battle station.
Both Tarkin and Tagge are prone to exaggerate the importance of the Death Star. Consequently, Vader chastises them:
Don't be too proud of this technological terror you've constructed. The ability to destroy a planet is insignificant next to the power of the Force.
The Death Star was a great symbol of fear, but the real power lay in the Sith use of the dark side of the Force, supplemented by the Imperial military.
As for why the Emperor waited so long to dissolve the Imperial Senate, remember that Vader had just captured Princess Leia -- a member of the Senate -- on the Tantive IV. This incident, in which a member of the Imperial Senate was caught aiding the Rebellion, gave the Emperor an excuse to disband the Imperial Senate. To avoid generating sympathy for the Rebellion by holding a senator captive, the official story was that the Tantive IV sent out a distress beacon and all aboard were killed (presumably after the Empire responded to the distress beacon only to discover that a senator was a member of the Rebel Alliance).