For one, strings are just chunks of memory like other arrays. So for almost any string that is not a literal in the source code, you just store offset/length as needed, like for any other array. I have sizeable projects (on the order of 10K lines) that have maybe 0 or 1 instances of strlen() in the code.
Very often though, strings are bounded and pretty short (since they are meant for human consumption), and in these cases, using strlen() when looking up a string is often sensible, since persisting the length might require more memory than the string itself.
Another case is when you're scanning the string from left to right anyway, so you just "stream" through it until you find the terminating 0. That's how printf() and friends work (they take a formatting string), and arguably this scheme works just fine.
Btw, the length of a string literal is (sizeof "Hello" - 1). You can also initialize char arrays using string literals and have the size available:
static const char name[] = "Foobar";
static const int nameLen = sizeof name - 1;