Real-life octopi can travel outside of water for awhile, but not permanently. My race is amphibious, living underwater primarily, but also coming up onto the surface if their environment becomes too dangerous, or food becomes scarce. I don’t want to them to be able to hold their breath for extended periods of time, but I could always go with that if nothing else would work I suppose. What biological factors would let them breathe both air and water?
Crustaceans and arachnids have managed to evolve lungs directly from gills, unlike tetrapods in which the primitive gill structures are homologous to various structural features in tetrapod skulls, and cephalopods could conceivably do the same.
The most significant innovation would be a means to keep the mantle chamber housing the gills inflated out of water, whether that be developing a full or partial internal shell, cartilaginous struts, or just suitably muscular mantle walls to hold their shape when not inflated with incompressible water.
At that point, the existing gill structures would be suitable for extracting oxygen from air as long as they are kept moist, which should be relatively simple since cephalopod gills are already internal. Heck, the same is true of human lungs--dry your lungs out, and you will not be happy! And in fact, part of the purpose of the sinus system is to hydrate inspired air before it hits the lungs. Your cephalopods may thus benefit from developing a longer path between the mantle opening and the gill surfaces.
As they start spending more time out of water, you may then see more specialization of the gill structures to processing air over water, analogous to the development of arthropod book lungs from book gills. Full adaptation to air breathing would involve further re-specialization to funnel air through smaller, higher-total-surface-area tracheal tubes, but that comes at the cost of no longer being able to efficiently process water with its much higher viscosity. To offset that, your cephalopods can benefit from one-way airflow from the mantle opening across the gas-exchange surfaces and out the siphon. Having mono-directional airflow across the gas exchange surfaces and properly optimized lungs together is, of course, the best option, as seen in birds, but you'll note that mammals get along fine with just one of those features (lung structures optimized for air over water)--your cephalopods should be just fine taking the alternate option (mono-directional airflow with less structural optimization).
EDIT: Note that snails and slugs, which are not cephalopods but, as mollusks, share their basic respiratory structure, have indeed adapted their mantle cavities into lungs for terrestrial life, and slugs are capable of inflating their lungs purely through muscular action, without a shell or cartilaginous structure to help support it.
Some fish, such as Betta Splendens (Betta fish), have what are called a Labyrinth organ that allows them to breath air. Its how they survive low oxygen environments when trapped in small, shallow ponds. When oxygen is low, they pop up to the surface and take a breath. Its not a true substitute for lungs (they can't stay out of water forever), but its a good survival technique.
So given that such a thing actually exists, its certainly within reason to accept that a cephalopod-like species might evolve something similar should their environment warrant it. For example, creatures that survive on coasts with large flood plains may find themselves in shallow puddles after a tide, and need to survive until the next tide comes in.
An intelligent race would learn to use that ability to venture deeper into land. Maybe not permanently, but certainly longer than other sea creatures can.
Evert their gills.
Octopi have gills they use for oxygen exchange. They are delicate so they are kept inside the mantle. They can push them out of the mantle to rinse them out - everting them. That is what this octopus is doing. The silvery thing is its gill.
On prolonged landwalks your cephalopods evert their gills and let them hang out in the air. It would look like a ruffly collar. They need to keep them wet and maybe they use tech to do this, or they could pull them back inside to re-wet them in an internal reservoir.
Symbiotic Relationships They have a friendly pet or plant that stores concentrated oxygen, or highly-oxygenated water, into a bladder. Your octopus carries the bladder, or a bandolier of them. The octopus must wear a water-containing mask over their gills (perhaps another over their eyes), and diffuse the oxygen into the water before attempting to breathe it.
Technology Assuming this is an intelligent race, they can move on from using natural external breathing sacs to crafted ones. Some creature or process still needs to create the oxygen, and some means of diffusing it into water is still needed before passing it over the gills.
Note that CO2 and CO buildup is still a significant problem in either case. If they are as susceptible as humans, then there is only a span of minutes before a handheld bladder becomes useless.
Early pioneers may discover fire from purified O2 to their dismay.