What brands do they stock?
As well as relationships with customers shops have to have relationships with suppliers. You will find that dealerships are not dished out so easily and only the best bike shops can have the best brands. This is for bikes and for components. A brand to look for is Specialized, does the shop have Specialized components? Customers will ask for Specialized by name and dealerships for components and bikes are limited, if they have Specialized then they have been established long enough to get the dealership. That is the situation in the UK but I do not know about everywhere else.
Appearances can be deceptive
Don't read too much into how cluttered or dusty the shop is. Few in the trade come from a merchandising background or have the time for ornate window displays. Tidy organised appearance is definitely a bonus but not the be-all and end-all.
How long do you have to wait?
We have all waited a lot longer in a bike shop to be served than seems sensible. Staff that care will be able to take a break from a complex touring bike sale to take money off you for that inner tube you just want to buy. Alternatively they will be able to point you in the direction of the products that you are interested in and make a promise to be with you soon. Because bike sales are so seasonal there will be busy periods when there are more customers than staff however a good shop will be able to mitigate walk-outs with simple P's and Q's.
Shops do not have the best interests of your wallet at heart
This may not be for the reasons you think. To you spending £100 on a bike might be big bucks but for the staff with a sea of bicycles in front of them £1000 may be nearer the mark for getting something to ride. When it comes to lights the set of £20 flashing LED's may be all you need but to the shop staff only the £150 brighter-than-the-sun light set makes sense.
It is for you to judge whether the shop is taking you for a ride or if the staff are on a bonus deal that means they get more money for fleecing you. There is no harm in being straight up and asking if they are working on commission if they are pointing you at the high-end products when you have walked in specifically after something more basic.
Equally, sales staff that lack confidence may not point you towards the better products. You may not care whether you spend £50 or £250 on a pair of shoes for that triathlon you hope to enter, what you don't want is for the shop to under-sell to you for you to end up with sub-standard products.
Don't expect the staff to be experts about everything
You may have pored over the catalogue all week and know the specifications inside and out, the shop staff may not have the time or the need to do that. You know information from over-browsing the catalogue, they have knowledge that means they only need the product knowledge necessary for what they do.
Some staff may be showroom only and be expert at sizing up kids bikes yet have no idea what chain you need for a nine speed or what pads you need for a vintage bike. They can even get a basic inner tube valve length wrong. Therefore make sure you know what you want in advance, don't rely on expert opinion in the shop and don't feel wronged if you know more than them about some particular thing.
Old parts off a repaired bike
Expect the shop to keep or bin parts that you have upgraded. If you have put your bike in for an inner tube repair do not expect the old tube back so that you can fix it. The same goes for a very expensive chainset. If you specifically want bits back then make sure you say so when the bike is booked in. It is standard practice in the UK for whatever happens to the old bits to be the bike-shop's prerogative, don't feel wronged if you do not get them back. Take a car analogy, if you took your car in for any work, would you expect the old bits back? No.
Workshop bookings
Most bike shops have a really bad system for workshop jobs. Spend some time on the phone and call your local shops to see what they can do for you. Do expect your bike to be wheeled in and out of the workshop into the rain to be potentially scratched and possibly damaged during that time it is in the workshop. Ask how your bike will be stored whilst it is booked in - nobody thinks to do that yet it is a big deal. You don't want your bike rustier and scratched more than before you booked it in for that simple service.
Also ask how long it is going to take. Then apply common sense if it is going to take a fortnight to 'change a tube'. This is not a question of trust, it is a question of workshop management. Some shops have a strict queue and it can get a bit long. Other shops will turn around what they can as soon as they can, ideally you want simple fixes, e.g. that cassette removed to be a while-you-wait task and not something you have to wait a fortnight for.
How well are the showroom bikes setup?
There is a tendency for bikes in showrooms to be somewhat loosely assembled. This is stupid as none of the bikes are at their best and it takes far longer to lazily assemble bikes to then have to completely check them over again. If the bikes are badly assembled in the showroom then they are not doing it right. Unless the prices are good go elsewhere.
One key indicator is the seat. Are the showroom bikes with the seats pointing at odd angles? This shows a lack of care and a lack of skill in the workshop. Coupled to that is a lack of understanding of what the customer wants - a comfy bike.
Some bikes, e.g. Brompton and to a certain extent Dahon, are fully assembled to top 'pre-delivery-check' standards in the factory. They don't need any further setting up. Showroom bikes should be to the same standard, every gear should work, every brake should work and every wheel should be properly in place. Handlebars may be twisted 90 degrees for space reasons and tyres may be soft due to inventory management reasons, however, all of the bikes in the shop should be in a ridable condition.
Is the shop part of a chain?
An owner-manager is more motivated than the hired-manager. He has to pay the bills every week and ensure the sales are taken care of properly. He will not stand for staff standing behind the counter and not assisting customers pro-actively.
On the other hand a hired manager of a chain will have career aspirations to make it into group management and a sales bonus to think of. A chain will also have a central warehouse and other bike sizes in other shops. Therefore the reputation of the chain is important.
You can get excellent staff in chains and single owner-manager shops. You can also get very bad staff. It is the luck of the draw whom you get to serve you. If you find that the salesperson is struggling, perhaps they don't actually go downhill mountain biking and know what you are after, in that case give them a break and ask if there is anyone in the staff team that knows a bit more about down-hill mountain bikes. This should not be taken the wrong way by them. Chances are that when you walked through the door their MTB supremo was dealing with another customer and he/she will be glad to spend time with you.
Do they offer to special order for you?
Not all sizes are stocked, not all parts are stocked. A good shop will offer to get whatever you need in, usually with less than a week turnaround. 'Sorry we don't stock that' is not a good enough answer, fobbing you off with the wrong product is not a good answer.
Can you test-ride a bike?
Bikes do get damaged with a ride around the block. However, for fast moving regular bikes there should be no problem with you going out on it to test ride. Expect to leave your keys and or wallet behind the till. Maybe expect an escort if you are comparing two bikes. Don't expect a test ride on the best bike in the shop though.
Can you borrow a spanner?
Shops should be able to lend you an Allen key to fit that water bottle that you just bought. If they cannot trust you with that then can you trust them?
What is in their car park at 9 a.m.?
Not all bike shop staff live and breathe bicycles. Chances are that the guy in the workshop is only working there to pay for his car. Ask staff if they actually ride. Although some say this does not matter, it does. Would you get a vegetarian working in a butchers to care about your sausages? Or a meat eater working in a organic-save-the-world-shop to have much of an opinion on lentils? Or an illiterate working in a book shop to help you find a good book about bikes? Or someone that hates music working in a record shop help you through the new releases?
If everyone in the bike shop drives to work then something is up. They too have heard the news about global warming, how cars give kids asthma, how the oil is running out, how dangerous cars are to cyclists, how wars get fought over oil and so on. Clearly they don't have the passion for the product to ride themselves. You have to ask why the bicycle is not good enough for them. They can live a long way away, be the older generation when motoring was aspirational or be one of those sad youngsters working just to pay for a car. Don't discredit them entirely for driving but bear it in mind.
What is in their car park after 9 a.m.?
Hopefully the shop has lots of customers and they all cannot be wrong to be shopping there. In some paces like the UK the success of a bike shop is pretty much down to if they have parking or not. Therefore the out of town shop with more parking, more warehouse space and a bigger showroom is a better bet but not always. Do ride out to the out of town shops and you will hopefully be pleasantly surprised.
What is their website like?
It can be hard for a shop to compete with the online specialists. However, does their shop clearly give the basic information. Opening hours? Brands stocked? A few words about the workshop? What their specialisms are? Do they give a first impression that is hopeful? They may not be experts at HTML - overlook that but not too much. The internet has been around for a decade or more, they should have some semblance of a webpage by now.
One area of trust is whether they do have a product focused website and if the prices match what you pay in the showroom. Go in with printouts and haggle if you get given a different price in the shop. Expect your trust to be diminished if there is no good reason for any discrepancies.
Conclusion
This question is as long as a piece of string. Opinions vary. Presented above is a far from exhaustive list of things to look out for. At the end of the day a lot comes down to personalities and whether you like the staff. That said there are things that may not come across in the time you spend with them and there may be good reasons for misunderstandings. Whatever, do support your local bike shop and be open to their service and expertise, not everything can be done online.