Well, you can ask them "are you PCI complaint?" However, you shouldn't take their answer at face value.

Recently, pretending to be a potential customer with an ecommerce website, I asked 10 random Linux hosts if their shared hosting plan was PCI compliant.

6 said "no" or "no, its not possible on a shared hosting plan", which for the most part is true, especially if its less than $50/mo.  As a general rule, you really should avoid looking at shared hosting all together if you are looking for the most secure and PCI compliant environment.

However 3 hosts said yes, they are PCI compliant on their Linux shared plans, which is rather hard to believe.  They also didn't elaborate on that, with the exception of one host who said their server would pass a PCI scan, which is just one aspect of PCI compiance.  This was quite shocking to me, and these companies most likely don't understand PCI compliance or were giving false information.

The 10th host said they were not familiar with PCI compliance. At least the were honest.

A few important requirements of PCI compliance to point out are:
1. The web site and database housing the credit card information need to be on seperate servers.  For example, your web server can be a Linux-based Apache web server and connect securely to a mySQL database server.  MySQL is not secure by default, so you will want to set up a secure tunnel, which you might do with Stunnel.
2. The database server must be on a private IP range.  This would be 10.x.x.x, 192.x.x.x, or 172.16.x.x
3. The database server must be behind a firewall.  To elaborate on the first point there should be a stateful hardware firewall, such as a Cisco ASA, between your web server and database server.
4. You must use a file integrity scanner to check your files, and the host must also scan the files at the OS level.  This should be run at least once daily, and someone needs to review the logs at least once a day as well.
5. Someone at the web hosting company needs to review the logs daily for abnormalities.  In addition to the file integrity logs, you will want to review other logs, such as the reports from LogWatch and PHPLogCon (PHPLogCon is the GUI for rsyslog).
6. Ask your host if they will help you create and provide sample documentation for the policies required by PCI Compliance, such as your Firewall Policy for PCI DSS requirement 1.1.3 and a policy required for each service you have running, and the port and protocol it uses.

That said, if a Linux web hosting provider says they are PCI compliant you will then want to ask some follow up questions, such as:
What will the IP of the database server be (or at least the first 2 octets of the IP if they don't want to tell you the whole IP)?
What type of firewall is between the web server and database server?  Is it hardware- or software-based?  Is it stateful or stateless?
Which file integrity scanner will be used to scan my site?  Will I be sent a copy of the reports automatically?  Can I see a sample report?
What is your schedule for reviewing the logs on the server?  What method do you use to notify a customer if you see an abnormality relating to their domain or username in the log?  How many different logs do you check daily?

When I asked the shared hosts who stated their plans were PCI compliant the questions above, they did not give favorable responses.  For example they would say the database is on a public IP but it won't allow connections from other public IP's unless you grant permission to allow connections from that IP.  Unfortunately, that wouldn't be acceptable: PCI complaince wants you to be extra cautious. Their rules require you to have a setup such that even if somehow an IP was granted permission or a wildcard was added, a connection could not be made. This by it's nature requires that the database be on a private IP.  Also if there was some type of remote exploit, a hacker could possibly bypass the IP ACL feature and gain access, where on a private network that would not be possible (at least not without exploiting another device first).  When asked if they reviewed logs daily, they would give answers such as "if we think we got hacked an admin will go and review the logs."  This is not acceptable. With PCI complaince you are supposed to review the logs anyway, so that you can catch the hacker before he gets in or before too much damage is done.

It's also important to note that simply passing a scan from a 3rd party PCI scanning service does not mean you have met all 12 requirements to be PCI compliant. Third party scans only check a small number of compliance regulations which can be determined from an external scan.

We asked Nick G. from PenguinWebHosting.com if he was PCI compliant, here was his response:
"With our dedicated servers and VPS solutions we offer a 17-point security package designed with PCI requirements in mind. We are also extremely  familiar with all 12 requirements of the PCI-DSS standards, as well as all sub-requirements. Specifially, we use a Cisco ASA 5505 hardware firewall which sits in between the web server (on a public network) and the database server (which is on a private network, usually on 10.0.x.x or 192.168.x.x IP block), we then create a secure tunnel from the web server to the database server. For file integrity scanning we are partial to the AIDE (Advanced Intrusion Detection Environment). We have security certified staff on hand to review the logs daily, and we also provide the client with a copy of the log summary.  This service is include with our PCI dedicated server  and VPS packages."

Bottom line there is a certain level of due dilligence the Payment Card Industry expects you to meet.  If you have a breach and credit card data is compromised, and you tell them, "Well my $4.95/mo host said I was PCI compliant so I just took their word for it and did not do anything extra on my end", they likely aren't going to have much sympathy for you.  On the other hand if you are able to show them you have created policies as they have directed, show you have set everything up as they have stated, have log reports and documentation showing those were reviewed, then you are going to have a much easier time with them.