The long and short answer is yes they do. The big question is how much it affects the tone and if it is an objective improvement to your subjective assessment. There isn't really a way to guarantee that X tube will make your amp brighter, darker, this or that. Some people say the first tube is the largest contributor to sound and some say the phase inverter tube is, or that the power tubes are. From my experience, the power tubes most certainly do have an effect, but there is just no way at all to predict what the effect will be. I had a Crate Blue DooDoo, it came with Groove Tubes in it, I swapped in a set of Sovtek's, and the amp didn't like it at all. went from already being a pretty bright and horrid amp to even worse of those symptoms. I have an 18-watt build that I designed and with cheap China tubes or nice Ruby tubes, it sounds the same. I also have an Egnater Tweaker-15 and it doesn't matter what tube I put in it, they all sound pretty much the same.
I think tubes are perhaps about 5-10% of the overall sound at best. The speakers are probably at least 50-60% or more of the overall sound. That leaves the last 45-30% a matter of everything else that there could potentially be. Heck, going from a 10' to a 20' guitar cord can alter the sound enough to be noticeable. How you bias the amp is a factor.
Tube rolling is an expensive adventure and thinking that NOS tubes will slay any modern-day tube is also a silly belief. Modern-day tubes are made just as well as they ever were. Old tubes sound the way they do simply because they were made 50 years ago. Not better, just different. The NOS market is what it is because they made you believe that they are superior. If they were that good then, why weren't they flying off the shelves? The only industry that keeps tubes in production is the music industry. So the only way to sell old stockpiles of unused tubes from the 1950s is to pawn them off onto new buyers under the guise of rarity. 50 years ago, there were dozens of different tube manufacturers. RCA, Phillips, Tung-Sol, Sovtek, Telefunken, and Mullard are only a few. Today there are only about 3-4 manufacturers who supply the entire world of rebranded tubes. JJ, Shuagang, and Reflektor are to the best of my knowledge the ONLY manufacturers currently producing tubes. Each of these companies has about 6 or more names you have heard and know of that rebrand the tubes. The notables read like this:
JJ = JJ, and Telefunken
Shuagang = Shuguang, Golden Dragon, and Sino
Reflektor = EH, Tung-Sol, Genalex and Sovtek.
So tell me now how you expect that a Tung-Sol and a Sovtek will sound different? Mesa rebrands tubes from all three manufacturers. Groove Tubes rebrands from all of them as well, as does TAD, Fender, Peavey, and Valve Art to name a few. There is a 33.33% chance that any given tube you buy from GT will come from any one or more of the 3 manufacturers. It is a tall stretch to say that a Sovtek tube will be better/different than a Tung-Sol tube, as they are made by the same parent company.
Where things do change is the grade of the tube and the style or version of it. A long plate 12AX7 will sound different than a short plate version. A 6L6GB is slightly different than a 6L6GC, which is different than a 6L6G, which is different from a 6L6GC-STR... The construction of a tube obviously creates a change in sound and each rebrander has a different way of marketing these constructions.
It has been found that tubes of today are about three times more expensive than what they would have been 50 years ago after factoring in inflation. Imagine now that you are paying $40 to $50 or more for a NOS tube made 50 years ago that would have sold for about 50 cents. After calculating inflation that same 50 cent tube would cost about $12-13 today. No matter how you cut it, it is still an old tube with no warranties and no guarantee of performance and life span.
I fear what will become of the NOS market in the years to come as the stockpile of these " special " tubes actually becomes non-existent. If buying the tube to use in an amp is sure to wear it out, what good is the tube going to be? When the cost of all the NOS tubes in your amp costs more than the amp itself, what will you do then? When will the madness stop? At some point, there is a 100% chance that there will be NO existing truly NOS tubes from the 1950s-60s era. Are we going to then start saying that tubes made in the 80s-90s are the new NOS tubes, special in every way and the must-have tube for your amp? It's absolute poppycock.
My suggestion is to let the rich kids and the bougie cork sniffers run the price of NOS tubes up to the point of stupidity and spend all that money. Meanwhile, focus on your playing and being sensible, reasonable, truthful, and practical with your purchases. If you truly are a player that is that good, and that the only way to be that much better is to have an amp made in the 1950s with tubes made in the 1950s, then, by all means, spend that $$$$. Unless you're playing in front of thousands of people, your tone is probably the least of your worries. Searching for tone for yourself is another thing, but I recommend you do it smartly. You do not need to spend insane amounts of money to get " that sound ", you just have to study what current tube constructions are available, what they do to affect the sound, and be realistic about the potential outcomes. A set of tubes are not going to take your amp from sounding like absolute crap to the best thing you've ever heard. They can only take it from absolute trash to being slightly better sounding trash. They may make a pretty good sounding amp sound subjectively better, but it will never take it from not holy grail to The Holy Grail.
I think that the speakers are the 100% best way to achieve a core change in sound. A cheap $100 practice amp doesn't sound like crap because the amp is crap, it sounds like that because the speaker is just as much a POS as the amp is. If you were to plug your crappy practice amp into a mid-grade speaker cabinet, I bet your opinion of the amp would change. Speakers are not exactly cheap, but they have decent resale value. If you buy $300 in speaker, you can probably recoup nearly half of that back on the sale of your old speakers. With enough studying, trials, and patience, you can probably get your desired sound within one or two speaker swaps, and in the end, only spend about the cost of 1, maybe two retubes would. Speakers are where the single largest change in amp sound will change. If your current amp sounds too bright, then get darker speakers. If your amp sounds too dull, get brighter speakers. etc. etc.