Understand the notion of 'tractability' in Graphical Models

I have seen these concepts being loosely used to give a sense of the computational complexity of computing marginals/evaluating the evidence on a graphical model; 'intractability' would mean these tasks are 'hard' (I think #P-hard would the appropriate thing to say in this case).

If I'm not mistaken, you can find a discussion on this in Wainwright and Jordan's book (pdf)

Basically, all known exact inference algorithms have in general worst-case time complexities that are exponential in some parameter of a given Bayesian network, or probabilistic graphical model. (typically it is the treewidth of the model)

Darwiche has a chapter on the computational complexity of different probabilistic reasoning tasks in his book. Roughly, if you can compute the MPE, then you can find satisfying assignments of a CNF (which is NP-complete). If you can compute the probability of evidence, then you can count the number of satisfying assignments (which is PP-complete, which basically contains NP and is at least as hard as finding a satisfying assignment).