Mark's parenthetical remark (viz., "In saying this Jesus declared all foods clean") and James's letter to Gentile Christians only appear to contradict each other. In fact, they can be harmonized quite easily. We need first to lay some groundwork before harmonizing them.
It is a given that Mark's words in his gospel and Luke's words in Acts are both part of inspired Scripture. The Holy Spirit moved both men to record the truth of God, and there can be no real contradiction between two or more passages in the Bible, only apparent contradictions. James's words as Luke records them in Acts 15 were also inspired by the Holy Spirit:
"For it seemed good to the Holy Spirit and to us to lay upon you [Gentile believers] no greater burden than these essentials . . ." (Acts 15:28).
I like the way James phrased this part of his letter: ". . . it seemed good to the Holy Spirit . . .," because the words indicate that James, the elders, and the whole church in Jerusalem were embroiled in a controversy which needed to be resolved right away. They therefore needed guidance from the Holy Spirit as to how to proceed, otherwise the fledgling--but expanding--churches in Judea and beyond were in danger of experiencing a paralyzing schism.
Luke tells us how this potential schism was instigated:
"Some men came down from Judea and began teaching the brethren, 'Unless you are circumcised according to the custom of Moses, you cannot be saved'" (Acts 15:1).
By analogy, imagine that in 2013 some ultra-conservative Christians in the Church of the Absolute Truth denomination (COTAT) are going from church to church insisting that any person with a tattoo cannot be saved and become a member of any local church in the COTAT denomination until he or she has the tattoo(s) removed surgically. Stay with me now!
These legalists--for want of a better term--are placing a burden on potential church members who in fact are born again but who offend these anti-tattooists within COTAT by having these "ungodly" tattoos on their flesh!
Personally, I am not a big fan of tattoos (I do not have one and do not plan to get one), but I would welcome into the fellowship of my local church anyone (man or woman) with a tattoo who also professes faith in Christ. I must add, however, that the leadership of my church has a God-given responsibility to inform all prospective members of some biblical criteria for membership within our local church. But I digress.
How, then, should the leadership of the various local churches within the COTAT denomination handle this looming controversy which threatens to divide the church into two camps: the exclusive anti-tattooists and the more-inclusive "It's OK to have a tattoo" faction?
Here is how the believers in the Jerusalem church handled their problem, which suggests how we might handle our tattoo controversy:
(1) They convened a meeting.
James, the elders, and the entire church in Jerusalem got together with church planters Paul and Barnabus, apostles to the Gentiles in the outlying regions of Israel. After an unsuccessful attempt of resolving the controversy through "no small dissension and debate" with the Judaizers (15:2), Paul and Barnabus decided wisely to take the issue to the denominational headquarters of "The Way" in Jerusalem.
The Bible tells us clearly, "in the multitude of counselors there is safety" (Proverbs 11:14; 15:22; 24:6). Barnabus and Paul recognized this principle and they joined key church leaders in Jerusalem to resolve the controversy.
The creation and fomentation of controversy within the local church is not of the Holy Spirit, whether the issue triggering the debate is tattoos or circumcision or dietary customs. God has not called us to schisms and rancor, but to peace and unity within the body.
"Let the peace of Christ rule [act as arbiter] in your hearts, to which indeed you were called in one body . . . (Colossians 3:15)."
(2) They sought guidance from the Word through the Holy Spirit.
Since it is imperative for Holy Spirit-filled leaders to exercise oversight in the practical, day-to-day affairs of the local church, they need to be informed by both the clear instructions of God's word regarding the non-negotiables of the faith, and a wise pragmatism to implement those instructions on a case-by-case basis.
One such "non-negotiable" principle is salvation by grace through faith. The Judaizers, who were much like the Pharisees and teachers of the law in Matthew 15 and Mark 7, were hung up on their own traditions and thereby effectively set aside a key foundational principle that salvation is "not of works, lest any man should boast" (Ephesians 2:8,9).
A wise man once said, "The challenge facing every local church can be summarized as follows: The main thing is to keep the main thing the main thing." Had the confabulation that convened in Jerusalem chosen to sweep the controversy under the rug, so to speak, the expansion of the church through conversions (see Acts 15:3) may have been imperiled. Is not "the main thing" to expand the church through conversions, baptism, and discipleship of all people-groups (Matthew 28:18-20)?
While "hot button" issues within the church may change over time and are certainly different from culture to culture, church leadership in every local church is to use discernment in "where they draw the line" between secondary, "grey" issues, and issues of great import and significance based on the clear teaching of God's word. In other words,
(3) They made a Holy Spirit-inspired, pragmatic, loving, God-honoring, and unanimous decision (see Acts 15:25).
That decision not only respected Jewish biblical traditions but at the same time recognized the "new thing" God was accomplishing in their midst; namely, the saving of Jews and Gentiles alike by His grace through faith alone, and not by grace through faith plus works.
In other words, the first-century church leaders in Jerusalem, all of whom were Jews (with very few exceptions) made their decision by a) respecting the Jewish majority in the body, who could say legitimately, "Hey, we were here first"; and b) by respecting the Gentile minority which would soon be a majority, who could say legitimately, "Hey, we weren't steeped in Jewish tradition, so it's not fair to make us play catch-up. Besides, aren't we saved by grace through faith alone and not by works?"
This principle of compromise is cause for stumbling, even among Christians today, as can be seen plainly in some of the other answers to the OP's question. That is why Paul was moved to write 1 Corinthians 8 and Romans 14 and 15, which provide us with guiding principles regarding our liberties in Christ. By providing Gentile believers with two dietary guidelines, James and the church in Jerusalem were not contradicting our Lord's declaring all foods to be clean; rather, they were encouraging the Gentiles to respect the scruples of their fellow believers who were Jews, years before the apostle Paul provided his Spirit-inspired guidelines in 1 Corinthians and Romans. As for the Judaizers, their false doctrine was nipped in the bud.
In conclusion, since none of us lives to himself or dies to himself (1 Cor 14:7) but are linked to other believers within Christ's body who may not share our freedoms concerning food, drink, and tattoos, we are to consider others' feelings and scruples before exercising our liberty in Christ. We all are free in Christ but at the same time are also bond-slaves of Jesus Christ, who did not come to please Himself but to do the will of Him who sent Him and to accomplish His work of ransoming sinners (Ro 15:3; Ma 20:28; Mk 10:45; Jn 4:34).
In summary, James et al. were not "laying down the law" in their letter to the Gentiles, thereby imposing a "greater burden" on them (Acts 15:19, 28), nor were they ignoring the scruples of the Jewish converts who had a great deal of un-learning to do. James et al. decided wisely to provide an interim solution to a temporary and divisive controversy. By doing so they set an example for us Christians today who may be struggling with contemporary and culture-specific controversies of our own almost 20 centuries later.
Now, who's up for getting a tattoo?