Today, sky coordinates are measured as "Right Ascension" (RA) and declination. These are similar to the angular coordinates we use for the Earth's surface but are measured on the celestial sphere relative to the celestial equator and pole. By using the current sidereal time, it is possible to map the local sky coordinates (ie. a horizontal bearing relative to true north, and an inclination above the horizon) to RA & Declination.
Brahe used devices such as Quadrants to measure this inclination. There's a engraving of one mounted to the side of a building (presumably at Uraniborg) at http://en.wikipedia.org/wiki/Uraniborg (Brahe did most of his observations at Stjerneborg due to problems with the Uraniborg instrument mountings).
As for time, the clocks of the day were accurate enough because the escarpment had been invented a couple of centuries earlier. A sidereal clock can be reset every night (using a known star and a meridian) so it only needs to be accurate for 24 hours. Temperature changes will be relatively limited in this period (and minimized further by resetting the clock twice a night), and there will be no motion. Yes the clocks would available to Brahe would be have been inaccurate compared to Harrison's chronometers of a few centuries later but Harrison was designing clocks to last months without adjustment and to survive violent motion and temperature changes.
Definitions:
Meridian: A great circle line that goes through the location (eg. Uraniborg Observatory) and the poles. It would be a line due south from Uraniborg. A star crosses the meridian when it is due south of the celestial pole.
Sidereal Clock: A sidereal clock is one that is synchronized with the stars and not the Sun. The Earth actually rotates in one sidereal day (about 4mins short of a normal day) but because it has moved a little bit in its orbit, the usual point of reference (the Sun) has moved slightly, hence the solar day is slightly longer than a sidereal day.
The modern solution would be to use a solar clock and then apply a correction based on the calendar (trivial with a microprocessor). But if you're dealing with mechanical clocks, it is just as easy to set the pendulum to run slightly fast.