Obviously, one can't use antibiotic resistance since they are not bacteria.
This is not so obvious. Some common antibiotics are active against archaea.1 The Halohandbook, an indispensable document for the propagation and transformation of Halobacteria, includes a list of selectable markers and their concomitant plasmids:

NovR, MevR, and TmR are genes conferring resistance to novobiocin, mevinolin, and trimethoprim, respectively.
Usually I would use NeoR and Neo plates but that won't work...
Without knowing the specific organism you are trying to clone, we can't know if neomycin resistance will work as a selectable marker. Indeed, the bacterial neomycin resistance gene Neo (encoding aminoglycoside-O-phosphotransferase) can be utilized by mammalian cells to reduce aminoglycoside toxicity2, so it's not a huge logical jump to assume that archaea could similarly use Neo. If you are working with Methanococcus, you can take advantage of vectors encoding aminoglycoside phosphotransferases native to Methanococcus voltae to select for neomycin resistance.3
References
- Khelaifia S, Drancourt M. Susceptibility of archaea to antimicrobial agents: applications to clinical microbiology. Clin Microbiol Infect. 2012 Sep;18(9):841-8.
- Dulon D, Ryan AF. The bacterial Neo gene confers neomycin resistance to mammalian cochlear hair cells. Neuroreport. 1999 Apr 26;10(6):1189-93.
- Argyle JL, Tumbula DL, Leigh JA. Neomycin resistance as a selectable marker in Methanococcus maripaludis. Appl Environ Microbiol. 1996 Nov;62(11):4233-7.