I want to be able to restrict access to some of the records from the global search of a custom object.
Any idea / suggestions?
If you wanted to completely block out an object, dont create a tab for it, and it doesn't show up in the search.
However, for all other cases, as long as the sharing settings permit the user to see the data, and if it matches the search expression, it will be returned in the results.
The question doesn't provide many details of what's the exact scenario but in general you need to start by reviewing your organization sharing settings: Organization Wide defaults, sharing rules, role hierarchy.
By not creating a tab as suggested in another answer you prevent this object showing up in the global search but it doesn't prevent accessing to those records directly or reporting on those records.