If we're talking about sea level reconstructions further back than we have tide records (i.e., direct measurement of average sea level in multiple places globally) or the modern where we primarily rely on satellite altimetry data (e.g., Strassburg et al., 2014), then there are a wide array of methods used to reconstruct sea level. A non exhaustive list:

1. Dating packages of specific types of coral reefs. Particular species of corals can only live within a very narrow range near sea level. If sea level rises, the existing corals will die (from lack of light) and the colony will move upward building on top of the old corals. If sea level lowers, the existing corals will die (from exposure) and the colony will move downward and build on the flanks of the old corals. If you then date the different packages of corals you have a relative sea level record. To make this an absolute record of sea level, you need to know something about the rate of rock uplift of the area to which the corals are rooted. Dating of packages of corals that are now completely above sea level along tectonically active coast lines, like Papua New Guinea, can be used to construct sea level curves if the rate of rock uplift can be constrained through a variety of other means (e.g., extrapolation of geodetic rates, low temperature thermochronology, etc). There are varieties of studies that estimate portions of the sea level curve through these means (e.g., Cutler et al., 2003, Chappell, 2002).

2. Backstripping sediment records. Basically looking at the stratigraphic records of sedimentary basins and using the record of subsidence (after accounting for sediment compaction and subsidence driven by tectonics) to work out the relative height of different packages which are tied to different sedimentary environments that may be relevant for sea level (e.g., Sahagian et al., 1996, Kominz, 1995, Levy & Christie-Blick, 1991, etc.)

3. Sequence stratigraphy as interpreted from seismic records. This is a methodology really pioneered by the oil industry using large 2D and 3D seismic sections of marine. These rely on identifying packages (sequences) and finding the geometric relations between their boundaries, i.e., onlap, offlap, etc., which provide indications of relative sea level through time (e.g., Christie-Blick, 1991). These techniques have been used to produce large-scale global estimates of sea level (e.g., Vail et al., 1977, Haq et al., 1987, Haq & Al-Qahtani, 2005).

4. Similar to the prior one, sequence stratigraphy applied to continental sedimentary records as opposed to seismic stratigraphy (e.g., Sloss, 1963, Ronov, 1994, Haq & Schutter, 2008 etc.)

5. Proxy records for ocean temperature and ice sheet volume. Specifically, marine oxygen isotope records (i.e., primarily the ratio of two stable isotopes of oxygen, ^(16)O and ^(18)O) preserved in a variety of ways (e.g., in the shells of marine microrganisms) are sensitive to the global volume of ice stored on land because during periods where large ice sheets are building, the ice becomes preferentially enriched in light ^(16)O whereas the oceans become enriched in heavy ^(18)O (e.g., this explainer from NASA). Thus reconstructing this ratio within the ocean as preserved in marine organism shells (where the age of these organisms are known through dating the sediment within which they are deposited) allows us to reconstruct the relative volume of ice and thus the sea level (along with associated data on temperature, etc). There lots of studies building out parts of the global sea level record using multiple independent oxygen isotope records, models, and a variety of other data (e.g., Waelbrock et al., 2002, Siddall et al., 2003, Miller et al., 2011, Grant et al., 2012, Rohling et al., 2014, De Boer et al., 2017, etc.).

6. Recently, new methods have been proposed such as using paleogeographic reconstructions (which themselves represent huge syntheses of stratigraphic, paleomangetic, and paleontological data) to construct sea level curves (e.g., Marcilly et al., 2022).

7. Combinations of portions of above. Many of the above references in fact already combine more than one type of record or proxy to reconstruct a portion of sea level variations. Additionally, there are a variety of efforts to combine as many records as possible to identify disagreements and similarities in these records and to produce as accurate composites as possible (e.g., Miller et al., 2005, Miller et al., 2020).

In summary, if you browse through many of these, you'll see that there are ranges of uncertainty and sets of assumptions for any individual method and the methods do not always agree in detail for specific time periods. However, broadly when comparing the sea level curves derived from different approaches (and using them to refine each other), we find a good amount of coherence and agreement. Thus, while the absolute magnitude of past sea level as estimated from these approaches is likely not completely correct, we have high confidence in the broad patterns and order of magnitude values.