We study the decoding of product codes and a class of parallel concatenated product codes (PCPC). PCPC improves the minimum distance while retaining the merit of low decoding complexity of turbo product codes (TPC). We prove that using the Fibonacci interleaver does help increasing the minimum distance. The regularity of the interleaver also reduces the implementation complexity and makes parallel interleaving feasible. We show that Pyndiah's algorithm for decoding product codes produce an annealing effect similar to that of the so-called annealed belief propagation (ABP) algorithms which adjusts the "temperature" of an augmented cost surface. Decoding methods based on modified Pyndiah and annealed BCJR algorithms for both PC and PCPC are proposed and their performance is compared.