A 3-to-8 decoder using AND and NOT gates takes a 3-bit binary input and activates one of eight outputs based on the input value. It uses NOT gates to generate the inverted versions of the input bits, and AND gates to create the output lines, where each output corresponds to a unique combination of input bits and their inversions.