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 start and a southern transect) 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.