This dish can easily be cooked (like gumbo), in a crock pot. I'll start the beans and onions and celery at night, and at some random point I'll add the pork. You can use pork shoulder, which is cheap and fatty; bacon and ham hocks are also good to use in red beans.
I also like to throw in a jalapeño or a few red chiles. Pour a small cup of strong coffee into your beans to give them a richer flavor.
I've had red beans served with smothered chicken or pork chops, if you've ever been to The Harbor in New Orleans you know just what I mean. Pig lips are optional.
The tradition of red beans on Monday comes from the fact that Monday is wash-day and red beans are easy to make and require little maintenance (really, just don't let them dry out). It also makes great free bar food.