I like using a soap and sponge, but it's not the only solution. It is possible to cut the weight of a soap and sponge setup pretty significantly. Using a small scrubby like the one shown below works well and is much lighter. You can also take a regular sponge and cut it into a much smaller mini-sponge which is typically still fine for the duration of a backpacking trip.
Soap can be decanted into a tiny container, like the Nalgene 1-oz bottle:
There are assorted biodegradable soaps which purport to be more environmentally friendly, although biodegradable soaps are not necessarily 100% environmentally friendly, especially if they end up in a water supply. The biodegradation typically only works in soils. If you're following LNT principles though, you should be washing over soils whenever possible as that will help prevent runoff into water sources and any tiny food particles are more likely to be broken down quickly in biologically active soil than in relatively lifeless dirt or rocks.
There are viable alternatives to soap and water though. One method which is fairly effective is to just clean with a bit of sand/grit to get the mechanical agitation required to remove food, then rinse with water as normal. This method may not be adequate though if your dishes have been used with meat. You can use a small amount of rubbing alcohol as a disinfectant after rinsing; the alcohol will evaporate very quickly.
Choice of cooking equipment can also affect how difficult it is to clean. Food will come off of non-stick pans easier than it comes off of some other materials, and making sure not to burn your food will also prevent the much more difficult cleaning which comes from that.
Pre-rinsing can also greatly reduce the amount of cleaning required. Putting a bit of warm water in your bowl and using your spoon to get gunk off the edges and bottom, then drinking (if you can bear it!) the soupy mixture which results gets more of the food in you and less to clean up.
Regardless of your cleaning procedures, you definitely should use purified drinking-quality water for at least the final rinse of your dishes. I always play it safe and use purified water for all dish washing, unless I specifically intend to boil water again in the same pot later for purification. You should also do all cooking and cleaning at least 200 feet away from any stream, trail, or campsite.