Yes, setting a cookie to remember that cookies were declined is the most appropriate approach. No, you usually shouldn't send this info to your backend.
Many cookies require consent because the ePrivacy directive (closely related to the GDPR) says that you can only access information on a user device if (a) that access is strictly necessary for the service requested by the user, or (b) if the user consented to the access. Analytics are not strictly necessary in this sense, so analytics cookies always require consent.
When declining consent, the user is presumably asking to not be bothered by further consent popups for the forseeable time (e.g. 6–12 months). In fact, bothering a user on every page could be considered a dark pattern, and would call in question whether any consent given after such pestering could even be valid.
Thus, there is a strong argument that setting a cookie to remember “consent declined” or “consent withdrawn” is strictly necessary to perform the service requested by the user.
Setting a cookie is usually the least invasive way to manage consent status. For a logged-in user, storing consent status on the backend could also be very sensible. Persisting consent status about a not-logged-in user is a bit pointless, and I don't think the GDPR requires this in any case – this might even go against the data minimization principle. You don't necessarily have to record or persist consent status, but you have to be able to “demonstrate” that consent has been given if you rely on that consent. That includes demonstrating both the aspect that this user has given consent (which could benefit from explicit records), but also the more general aspect that this consent was obtained in a valid manner.