The Nero in the name obviously refers to the colour of the grapes. d'Avola refers to the town and region of Avola in the south-eastern part of Sicily where this variety produces some fine wines.
Although Nero d'Avola has an alternative name of Calabrese suggesting its origin on the neighboring mainland region of Italy it is doubtful if the variety was ever grown there. This issue is discussed at length in Jancis Robinson's 2012 publication Wine Grapes
Nero d'Avola is favoured in warmer climates for two reasons. Firstly as a late ripening variety the critical last month of maturation is more likely to be after the hottest part of summer. Steady ripening in this last few weeks of the growing season is a major factor in wine quality.
Secondly the variety seems to be less susceptible to berry damage during heat waves.
I believe this variety has a huge future in Australia. It is suitable for most of the warmer areas of this country and will quickly break out from it's current habitat of mainly McLaren Vale in South Australia.
A possible limitation of the variety is its susceptibility to fungal diseases so that it may not do well in regions where there is rain at harvest time.
Spaghetti puttanesca with a spicy tomato based sauce might be one match you could try, or perhaps grilled Italian fennel sausages...
Arancini are rice and meat balls and a favourite in Sicily.
Nero d'Avola wines are sometimes likened to Shiraz. I think that the likeness is fairly rough, but it gives you an idea about the range of foods to consider.
You can add your location to the search results and you will get a list of retailers near you, or you can find online merchants.
In 2014 seventeen entries were judged with the following results