My question is this: Does electrolysis work the same way when the cathode and anode are made of the same metal? It might be a stupid question, but I can't find anything that answers this question specifically.
The battery or the power source does not care about the electrode material. Its job is to pump the electrons in the circuit. Now the problems originate from the chemistry rather. By definition, if a direct current passes through an electrolyte, electrolysis (=chemical decomposition) has to occur. Something has to reduce at the cathode and something has to oxidize at the anode. Here, we enter the competition, as shown below in the case of your simple aqueous NaCl set up.
At the anode (the electrode connected to the positive terminal of the DC supply), you have to think...
(a) Will the electrode oxidize itself? Possible
(b) Will the solvent i.e., water oxidize to oxygen? Possible
(c) Will the chloride ion oxidize to chlorine? Possible
(d) Na+ ions, they should be repelled
(e) Can the electrode react with the electrolytic product? Very much possible
Similarly at the cathode (the electrode connected to the negative terminal of the DC supply), think about ...
(a) Can the electrode reduce itself? If it is a metal, it cannot reduce further.
(b) Will the solvent i.e., water reduce to hydrogen? Possible
(c) Can the Na+ ions be reduced to metallic sodium? Possible, but not in plain water.
(d) Cl- should be pushed away.
(e) Can the electrode react with the electrolytic products? Very much possible
So you can see here, that depending on the electrode material, yes it can be oxidized if used an anode. It can also be oxidized indirectly, if the evolving chlorine begins to attack the metal, which happened in your case.
In any case, electrolytic cell does not care about the electrodes, the electrodes can certainly be the same but they have to be inert. People always choose inert electrodes so that the metallic cathode or anode do not interfere chemically during the electrolysis. Platinum is a good choice but it is too expensive for home experiments. Carbon/graphite electrode is another choice. As you have seen, stainless steel is not a good choice as an anode. It is readily oxidized by chlorine.